P4211 [LNOI2014]LCA
链接
思路
多次询问\(\sum\limits_{l \leq i \leq r}dep[LCA(i,z)]\)
可以转化成l到r上的点到根的路径+1 最后求一下1到z的路径和就是所求 区间\([l,r]\)是可以差分的 离线直接求就行了。 树剖常数小，但还是比LCT多个log代码
#include#define ls c[x][0]#define rs c[x][1]using namespace std;const int N = 1e5 + 7, mod = 201314;int read() { int x = 0, f = 1; char s = getchar(); for (;s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1; for (;s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0'; return x * f; }int f[N], c[N][2], w[N], siz[N], sum[N], stak[N], lazy[N], lazytwo[N];bool isroot(int x) {return c[f[x]][0] == x || c[f[x]][1] == x;}void tag(int x){swap(ls,rs), lazy[x] ^= 1;}void tagtwo(int x, int val) { sum[x] = (sum[x] + 1LL * val * siz[x] % mod) % mod; w[x] = (w[x] + val) % mod; lazytwo[x] = (lazytwo[x] + val) % mod;}void pushdown(int x) { if (lazy[x]) { if (ls) tag(ls); if (rs) tag(rs); lazy[x] ^= 1; } if (lazytwo[x]) { if (ls) tagtwo(ls, lazytwo[x]); if (rs) tagtwo(rs, lazytwo[x]); lazytwo[x] = 0; }}void pushup(int x) { sum[x] = (sum[ls] + sum[rs] + w[x]) % mod; siz[x] = siz[ls] + siz[rs] + 1;}void rotate(int x) { int y = f[x], z = f[y], k = c[y][1] == x, w = c[x][!k]; if (isroot(y)) c[z][c[z][1] == y] = x; c[x][!k] = y; c[y][k] = w; if (w) f[w] = y; f[x] = z; f[y] = x; pushup(y);}void splay(int x) { int y = x, z = 0; stak[++z] = y; while (isroot(y)) stak[++z] = y = f[y]; while (z) pushdown(stak[z--]); while (isroot(x)) { y = f[x], z = f[y]; if (isroot(y)) rotate((c[y][0] == x)^(c[z][0] == y) ? x : y); rotate(x); } pushup(x);}void access(int x) { for (int y = 0; x;x = f[y = x]) splay(x), rs = y, pushup(x);}void makeroot(int x) { access(x), splay(x); tag(x);}int findroot(int x) { access(x), splay(x); while(ls) pushdown(x), x = ls; return x;}void split(int x, int y) { makeroot(x), access(y), splay(y);}void link(int x, int y) { makeroot(x); if (findroot(y) != x) f[x] = y;}void cut(int x, int y) { makeroot(x); if (findroot(y) == x && f[x] == y && !rs) { f[x] = c[y][0] = 0; pushup(y); }}struct node { int id, l, z, ans; node(int a = 0, int b = 0, int c = 0) { id = a, l = b, z = c; }} Q[N];bool cmp1(const node &a, const node& b) { return a.l < b.l;}bool cmp2(const node &a, const node& b) { return a.id < b.id;}int main() { // freopen("a.in", "r", stdin); int n = read(), m = read(); for (int i = 2; i <= n; ++i) { int x = read() + 1; link(i, x); } for (int i = 1; i <= m; ++i) { int l = read() + 1, r = read() + 1, z = read() + 1; Q[i * 2 - 1] = node(i * 2 - 1, l - 1, z); Q[i * 2] = node(i * 2, r, z); } m <<= 1; sort(Q + 1, Q + 1 + m, cmp1); int js = 1; for (int i = 0; i <= n; ++i) { if (i) split(1, i),tagtwo(i, 1); while(Q[js].l == i) { split(1, Q[js].z); Q[js].ans = sum[Q[js].z]; js++; } } sort(Q + 1, Q + 1 + m, cmp2); for (int i = 2; i <= m; i += 2) { int ans = Q[i].ans - Q[i - 1].ans; ans = (ans % mod + mod) % mod; printf("%d\n", ans); } return 0;}