题解 P3676 【小清新数据结构题】

Nemlit

2019-09-24 19:54:50

Solution

首先我们要发现一个性质,对于每一棵树,我们换了一个根(把原本根的某个儿子$v_1$记成新的根) 我们记这个树的权值和为sum,每个子树的权值和为$S[i]$,对于每次换根,受影响的$S[i]$只有根本身和$v_1$,并且满足:$S[rt]->sum - S[v_1]$, $S[v_1] -> S[rt]$ 于是我们能惊人的发现:$\sum (sum - S[i]) * S[i]$是一个定值!!! 把他拆开:$sum * \sum S[i] - \sum S[i] ^ 2$ 而我们要求的正是$\sum S[i] ^ 2$,于是我们只要维护$sum * \sum S[i]$ 因为我们会修改权值,发现$sum$值很好维护,于是我们只需要维护$\sum S[i]$即可 我们假设以x为根,那么$\sum S[i] = \sum (dep[i] + 1) * val[i] = sum + \sum dep[i] * val[i]$ 若我们不用重新求$dep$,柿子即化为:$\sum S[i] = sum + \sum val[i] * dis(i, x) $ 这个式子就是动态点分治的模板了,但是我们其实还有一个问题:就是我们的那个定值($\sum (sum - S[i]) * S[i]$)要怎么求呢? 我们还是对每个点分开考虑:上述柿子的意义实际上是求出所有点的子树和 * (总的子树和 - 该点子树和) 我们分开考虑每一对点$(i, j)$的贡献,即两个点被分在不同集合的个数*权值之积 于是这个式子其实可以转化为$\sum_{i = 1}^n\sum_{j = i+ 1}^nval[i] * val[j] * dis(i, j)$ 把$val[i]$提前,我们得到:$\sum_{i = 1} ^ n val[i] * \sum_{j = i + 1} ^ n val[j] * dis(i, j)$ 所以每一次修改($a[x] \to y$),变化量即为$(y - a[x]) *\sum val[j] * dis(j, i)$ 这不就是$\sum S[i]$吗??? 于是,我们就可以得到: $$\sum (sum - S[i]) * S[i] = sum * \sum S[i] - \sum S[i] ^ 2$$ $$\sum S[i] ^ 2 = sum * \sum S[i] - \sum (sum - S[i]) * S[i]$$ $sum - 1$直接维护,$\sum S[i]$用动态点分治来维护,后面那一堆我们可以根据$\sum S[i]$来维护,于是我们就做完了。 终于把咕了一年多的代码补上了。 ```cpp /* This code is written by Nemlit */ #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define rep(i, a, b) for(re int i = (a); i <= (b); ++ i) #define Next(i, u) for(re int i = head[u]; i; i = e[i].next) #define int long long il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define maxn 200005 int head[maxn], cnt, n, m, rt, N, A[maxn], vis[maxn], S, temp, R, a[maxn], w[maxn], f[maxn], Fa[maxn], g[maxn], dp[maxn]; int son[maxn], fa[maxn], dep[maxn], size[maxn], top[maxn]; struct edge { int v, next; }e[maxn << 1]; il void add(int u, int v) { e[++ cnt] = (edge){v, head[u]}, head[u] = cnt; } il int LCA(int u, int v) { while(top[u] != top[v]) dep[top[u]] > dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]]; return dep[u] > dep[v] ? v : u; } il void dfs1(int u, int fr) { size[u] = 1, fa[u] = fr, dep[u] = dep[fr] + 1; Next(i, u) { int v = e[i].v; if(v == fr) continue; dfs1(v, u), size[u] += size[v]; if(size[son[u]] < size[v]) son[u] = v; } } il void dfs2(int u, int fr) { top[u] = fr; if(son[u]) dfs2(son[u], fr); Next(i, u) { int v = e[i].v; if(v == fa[u] || v == son[u]) continue; dfs2(v, v); } } il int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[LCA(u, v)]; } il void get_rt(int u, int fr) { dp[u] = 0, size[u] = 1; Next(i, u) { int v = e[i].v; if(vis[v] || v == fr) continue; get_rt(v, u), size[u] += size[v], dp[u] = max(dp[u], size[v]); } dp[u] = max(dp[u], N - size[u]); if(dp[u] < dp[rt]) rt = u; } il void build(int u) { vis[u] = 1; Next(i, u) if(!vis[e[i].v]) dp[rt = 0] = n, N = size[e[i].v], get_rt(e[i].v, u), Fa[rt] = u, build(rt); } il int query(int x) { int ans = f[x], now = x; while(now != R) ans += (f[Fa[now]] - g[now]) + (w[Fa[now]] - w[now]) * dist(x, Fa[now]), now = Fa[now]; return ans; } il void insert(int x, int o) { int now = x, pax = o; o = A[x] - o, A[x] = pax; while(now != R) w[now] += o, f[now] += o * dist(x, now), g[now] += o * dist(x, Fa[now]), now = Fa[now]; w[R] += o, f[R] += o * dist(x, R), temp += 2 * query(x) * o, S += o; } signed main() { n = read(), m = read(); rep(i, 2, n) { int u = read(), v = read(); add(u, v), add(v, u); } dfs1(1, 0), dfs2(1, 1), dp[rt = 0] = N = n, get_rt(1, 0), R = rt, build(rt); rep(i, 1, n) insert(i, read()); rep(i, 1, m) { int opt = read(), x = read(); if(opt == 1) insert(x, read()); else printf("%lld\n", (S + query(x)) * S - temp / 2); } return 0; } ```