[BZOJ3626][LNOI2014]LCA（离线处理+树剖+线段树）

Address

https://www.lydsy.com/JudgeOnline/problem.php?id=3626

Solution

下面强制使点的编号从 1$1$ 开始计数。
先考虑一个简单问题：
在一棵树上，给定一些黑点，每次给出一个点 u$u$ ，求：

∑v是黑点dep[LCA(u,v)]$$\sum _{v是黑点}dep[\text{LCA}(u,v)]$$

容易想到将枚举黑点 v$v$ 转化为枚举 LCA$\text{LCA}$ 的深度：

∑i=1dep[u]i×(s[p[i]]−s[p[i+1]])$$\sum _{i=1}^{dep[u]}i\times (s[p[i]]-s[p[i+1]])$$

p[i]$p[i]$ 为根到 u$u$ 的路径上深度为 i$i$ 的点， s[u]$s[u]$ 表示 u$u$ 的子树内黑点个数。
特别地， s[p[dep[u]+1]]=0$s[p[dep[u]+1]]=0$ 。
把上式化一下：

∑i=1dep[u]i×s[p[i]]−∑i=1dep[u]−1i×s[p[i+1]]$$\sum _{i=1}^{dep[u]}i\times s[p[i]]-\sum _{i=1}^{dep[u]-1}i\times s[p[i+1]]$$

=∑i=1dep[u]i×s[p[i]]−∑i=1dep[u](i−1)×s[p[i]]$$=\sum _{i=1}^{dep[u]}i\times s[p[i]]-\sum _{i=1}^{dep[u]}(i-1)\times s[p[i]]$$

=∑i=1dep[u]s[p[i]]$$=\sum _{i=1}^{dep[u]}s[p[i]]$$

于是，只需要维护每个节点的 s$s$ 之后，查询 u$u$ 到根路径上所有点的 s$s$ 之和即可。
回到问题。将一个询问拆成两个：
（1）将 [1,l−1]$[1,l-1]$ 内的点设为黑点，其他为白点。
（2）将 [1,r]$[1,r]$ 内的点设为黑点，其他为白点。
拆询问之后将形如 [1,x]$[1,x]$ 的询问按照 x$x$ 离线排序。
这样，就能从 1$1$ 到 n$n$ 动态地加入黑点并询问了。
把 u$u$ 变成黑点后， u$u$ 到根的路径上所有点的 s$s$ 加上 1$1$ 。
所以，我们要实现路径加一和路径求和操作。
用 树剖 + 线段树 可以实现。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Tree(u) for (int e = adj[u], v; e; e = nxt[e]) if ((v = go[e]) != fu)
#define p2 p << 1
#define p3 p << 1 | 1
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
typedef long long ll;
const int N = 5e4 + 5, M = N << 1, L = M << 1, PYZ = 201314;
int n, q, ecnt, nxt[M], adj[N], go[M], fa[N], dep[N], sze[N],
son[N], top[N], dfn[N], QAQ, QWQ, add[L], ans[N]; ll T[L];
struct cyx {
    int i, u, id;
} orz[M];
bool comp(cyx a, cyx b) {
    return a.i < b.i;
}
void add_edge(int u, int v) {
    nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
    nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
}
void dfs1(int u, int fu) {
    dep[u] = dep[fa[u] = fu] + (sze[u] = 1);
    Tree(u) {
        dfs1(v, u); sze[u] += sze[v];
        if (sze[v] > sze[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int fu) {
    if (son[u]) {
        top[son[u]] = top[u];
        dfn[son[u]] = ++QAQ;
        dfs2(son[u], u);
    }
    Tree(u) {
        if (v == son[u]) continue;
        top[v] = v; dfn[v] = ++QAQ;
        dfs2(v, u);
    }
}
void init() {
    dfs1(1, 0); QAQ = top[1] = dfn[1] = 1;
    dfs2(1, 0);
}
void down(int p) {
    add[p2] += add[p]; add[p3] += add[p];
    add[p] = 0;
}
void upt(int l, int r, int p) {
    int mid = l + r >> 1;
    T[p] = T[p2] + 1ll * (mid - l + 1) * add[p2]
        + T[p3] + 1ll * (r - mid) * add[p3];
}
void change(int l, int r, int s, int e, int v, int p) {
    if (l == s && r == e) return (void) (add[p] += v);
    int mid = l + r >> 1; down(p);
    if (e <= mid) change(l, mid, s, e, v, p2);
    else if (s >= mid + 1) change(mid + 1, r, s, e, v, p3);
    else change(l, mid, s, mid, v, p2),
        change(mid + 1, r, mid + 1, e, v, p3);
    upt(l, r, p);
}
ll ask(int l, int r, int s, int e, int p) {
    if (l == s && r == e) return T[p] + 1ll * (r - l + 1) * add[p];
    int mid = l + r >> 1; down(p); ll res;
    if (e <= mid) res = ask(l, mid, s, e, p2);
    else if (s >= mid + 1) res = ask(mid + 1, r, s, e, p3);
    else res = ask(l, mid, s, mid, p2) +
        ask(mid + 1, r, mid + 1, e, p3);
    return upt(l, r, p), res;
}
void path_change(int u, int v, int w) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        change(1, n, dfn[top[u]], dfn[u], w, 1);
        u = fa[top[u]];
    }
    if (dfn[u] > dfn[v]) swap(u, v);
    change(1, n, dfn[u], dfn[v], w, 1);
}
ll path_ask(int u, int v) {
    ll res = 0; while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += ask(1, n, dfn[top[u]], dfn[u], 1);
        u = fa[top[u]];
    }
    if (dfn[u] > dfn[v]) swap(u, v);
    return res + ask(1, n, dfn[u], dfn[v], 1);
}
int main() {
    int i, l, r, x, p = 1; n = read(); q = read();
    For (i, 2, n) x = read() + 1, add_edge(x, i);
    init(); For (i, 1, q) {
        l = read() + 1; r = read() + 1; x = read() + 1;
        orz[++QWQ] = (cyx) {l - 1, x, QWQ};
        orz[++QWQ] = (cyx) {r, x, QWQ};
    }
    sort(orz + 1, orz + QWQ + 1, comp);
    For (i, 1, QWQ) {
        if (!orz[i].i) continue;
        while (p <= orz[i].i) path_change(1, p, 1), p++;
        int res = path_ask(1, orz[i].u);
        if (orz[i].id & 1) ans[(orz[i].id - 1 >> 1) + 1] -= res;
        else ans[(orz[i].id - 1 >> 1) + 1] += res;
    }
    For (i, 1, q) printf("%d\n", ans[i] % PYZ);
    return 0;
}