[LNOI2014] LCA 题解

Shiroyowaii · 2023-12-06 11:12:36 · 个人记录

题目链接

题目大意：

给出棵根为 1 的树，每次询问给出 l, r, x， 求 \sum_{i=l}^r dep(lca(i, x))。

Sol：

因为 l\sim r 的 lca 不一样，不好直接求 dep，所以要用到树上 lca 的常见变形：

求 \sum_{i=l}^r dep_x + dep_i 是平凡的，所以问题变为求 \sum_{i=l}^r dis(x, i)。

这是比较经典的点分树题。

因为点分树有着两个强大的性质：

1.树高为 \log(n)。

2.分树上两点的 lca，一定在原树两点的路径上。

因此，x 与 i 的 lca 只有 \log 种，dis(x, i) = dis(x,lca) + dis(i, lca)。

具体的，我们可以维护出 g_u 表示点分树上 u 子树内存在的点到 u 的 dis 值和，h_u 表示点分树上 u 子树内存在的点到 fa_u 的 dis 值和，sg_u 表示点分树上 u 子树内存在的点的个数。

加点删点都是修改点分树上的祖先，所以是 \log 的。

查询时用 g, h 容斥可算出 \sum dis(i, lca)，再用 sg 求出 dis(x, lca)即可。

因为有 l, r 的限制，而且满足可减性，所以考虑离线扫描线，将询问拆成 1\sim l-1 和 1\sim r，枚举到 j 时，将 j 加入点分树，查询右端点为 j 的询问即可。

实现时，求原树两点的距离用 dfn 序 O(1) 求 lca。

最后时间复杂度为 O((n+m)\log(nm)) 。

code：

#include <bits/stdc++.h>

#define For(x, y, z) for (int x = y, x##E = z; x <= x##E; ++x)
#define Rof(x, y, z) for (int x = y, x##E = z; x >= x##E; --x)
#define Eor(u) for (int i = head[u]; i; i = nxt[i])
#define SZ(x) (int(x.size()))
#define pb push_back

using namespace std;
using i64 = long long;

char buf[(1<<21)+5],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

inline int read() {
    int x = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}

const int N = 5e4 + 1000;

int n, m; i64 sdep[N], ans[N];
int head[N], nxt[N << 1], to[N << 1], cnt;

void Add(int u, int v) {
    to[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
    to[++cnt] = u, nxt[cnt] = head[v], head[v] = cnt;
}

int fa[N], dep[N], dfn[N], num, lg[N], f[17][N];

void dfs(int u) {
    dep[u] = dep[fa[u]] + 1, f[0][dfn[u] = ++num] = fa[u];
    Eor(u) if (to[i] != fa[u]) dfs(to[i]);
}
int Min(int x, int y) { return dfn[x] < dfn[y] ? x : y; } 
int dis(int x, int y) { if (x == y) return 0;
    int ans = dep[x] + dep[y]; x = dfn[x], y = dfn[y];
    if (x > y) swap(x, y); int l = lg[y - (x++)];
    return ans - 2 * dep[Min(f[l][x], f[l][y - (1 << l) + 1])];
}
namespace DCD{
    int Root, siz[N], maxp[N], Fa[N], root; bool vis[N];
    void get_root(int u, int f, int total) {
        siz[u] = 1, maxp[u] = 0;
        Eor(u) if (!vis[to[i]] && to[i] != f) {
            get_root(to[i], u, total), siz[u] += siz[to[i]];
            maxp[u] = max(maxp[u], siz[to[i]]);
        } maxp[u] = max(maxp[u], total - siz[u]);
        if (maxp[u] < maxp[root]) root = u;
    } 
    int build(int u, int total) { 
        root = 0, get_root(u, 0, total);
        get_root(u = root, 0, total), vis[u] = 1;
        Eor(u) if (!vis[to[i]]) Fa[build(to[i], siz[to[i]])] = u; 
        return u;
    }
    i64 g[N], h[N]; int sg[N];
    void modify(int u) {
        for (int x = u, y = 0, d; x; y = x, x = Fa[x]) 
            d = dis(u, x), g[x] += d, ++sg[x], h[y] += d;
    }
    i64 ask(int u) { i64 ans = 0;
        for (int x = u, y = h[0] = 0, d; x; y = x, x = Fa[x]) 
            d = dis(x, u), ans += g[x] - h[y] + 1ll * (sg[x] - sg[y]) * d;
        return ans;
    }
}

struct node {
    int x, u, id, op;
    bool operator<(const node &b) const {
        return x < b.x;
    }
}q[N << 1];

signed main() {
    n = read(), m = read();
    For(i, 2, n) Add(fa[i] = read() + 1, i);
    For(i, 2, n) lg[i] = lg[i >> 1] + 1;

    dfs(1);  For(i, 1, lg[n]) For(j, 1, n + 1 - (1 << i))
        f[i][j] = Min(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
    For(i, 1, n) sdep[i] = sdep[i - 1] + dep[i];

    DCD::maxp[0] = n + 1, DCD::Root = DCD::build(1, n);

    For(i, 1, m) {
        int l = read() + 1, r = read() + 1, x = read() + 1;
        q[i] = {l - 1, x, i, 1}, q[i + m] = {r, x, i, -1};
        ans[i] = sdep[r] - sdep[l - 1] + (r - l + 1ll) * dep[x];
    }
    sort(q + 1, q + 2 * m + 1); int j = 0;
    For(i, 0, n) { if (i) DCD::modify(i);
        while (j < 2 * m && q[j + 1].x <= i) 
        ++j, ans[q[j].id] += DCD::ask(q[j].u) * q[j].op;
    }
    For(i, 1, m) cout << ans[i] / 2 % 201314 << '\n';
    return 0;
}