[COJ0970]WZJ的数据结构（负三十）

试题描述

给你一棵N个点的无根树，点和边上均有权值。请你设计一个数据结构，回答M次操作。

1 x v：对于树上的每一个节点y，如果将x、y在树上的距离记为d，那么将y节点的权值加上d*v。

2 x：询问节点x的权值。

输入

第一行为一个正整数N。

第二行到第N行每行三个正整数ui,vi,wi。表示一条树边从ui到vi，距离为wi。

第N+1行为一个正整数M。

最后M行每行三个或两个正整数，格式见题面。

输出

对于每个询问操作，输出答案。

输入示例

101 2 21 3 11 4 31 5 24 6 24 7 16 8 17 9 27 10 191 3 11 10 12 12 42 51 5 11 8 12 22 9

输出示例

66102224

数据规模及约定

对于30%的数据：1<=N,M<=1000

另有50%的数据：1<=N,M<=100000，保证修改操作均在询问操作之前。

对于100%的数据：1<=N,M<=100000，1<=x<=N，1<=v,wi<=1000

题解

新姿势 get：动态点分治。

其实我也不知道为啥叫“动态”点分治。

首先这道题可以转化一下，对于每个节点我们不直接记录题目要求的答案，我们可以把修改操作转化成“给节点 x 的权值加上 v”，那么询问就变成了“求树上所有点到节点 x 的加权距离（就是对于所有的节点 u 求 sigma( D[u] · dist(u, x) )，这里的 D[u] 表示节点 u 的权值，dist(a, b) 表示树上路径 (a, b) 的边权总和）”。注意到边权永远是固定的。

我们可以建立出“重心树”，就是先点分治一波，然后我们把每一层分治的中心连到一块形成的新的树形结构。然后我们维护这棵树的子树信息：val[u] 表示节点 u 为根的子树中点权和；distv[u] 表示节点 u 的子树中所有点到 u 的加权距离和（注意这里加权距离是在原树上的）；distfa[u] 表示节点 u 的子树中所有到 fa[u] 的加权距离和（注意这里加权距离是在原树上的，而 fa[u] 是重心树上 u 的父亲结点）。

然后我们就发现每次修改和询问都是可以 O(logn) 实现的。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f;}#define maxn 100010#define maxm 200010#define maxlog 19#define LL long longint n, m, head[maxn], nxt[maxm], to[maxm], dist[maxm];void AddEdge(int a, int b, int c) { to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m; swap(a, b); to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m; return ;}int dep[maxn], mnd[maxlog][maxn<<1], Log[maxn<<1], clo, pos[maxn];void build(int u, int pa) { mnd[0][pos[u] = ++clo] = dep[u]; for(int e = head[u]; e; e = nxt[e]) if(to[e] != pa) dep[to[e]] = dep[u] + dist[e], build(to[e], u), mnd[0][++clo] = dep[u]; return ;}void rmq_init() { Log[1] = 0; for(int i = 2; i <= clo; i++) Log[i] = Log[i>>1] + 1; for(int j = 1; (1 << j) <= clo; j++) for(int i = 1; i + (1 << j) - 1 <= clo; i++) mnd[j][i] = min(mnd[j-1][i], mnd[j-1][i+(1<
           
             r) swap(l, r); int t = Log[r-l+1]; return ans - (min(mnd[t][l], mnd[t][r-(1<
            
             << 1);}int rt, size, f[maxn], siz[maxn];bool vis[maxn];void getroot(int u, int pa) { siz[u] = 1; f[u] = 0; for(int e = head[u]; e; e = nxt[e]) if(to[e] != pa && !vis[to[e]]) { getroot(to[e], u); siz[u] += siz[to[e]]; f[u] = max(f[u], siz[to[e]]); } f[u] = max(f[u], size - siz[u]); if(f[rt] > f[u]) rt = u; return ;}int fa[maxn];void solve(int u) { vis[u] = 1; for(int e = head[u]; e; e = nxt[e]) if(!vis[to[e]]) { f[rt = 0] = size = siz[u]; getroot(to[e], u); fa[rt] = u; solve(rt); } return ;}int val[maxn];LL distv[maxn], distfa[maxn];void update(int s, int v) { for(int u = s; u; u = fa[u]) { val[u] += v; if(fa[u]) { int d = cdist(fa[u], s); distv[fa[u]] += (LL)d * v; distfa[u] += (LL)d * v; }// printf("%d: %lld %lld\n", u, distv[u], distfa[u]); } return ;}LL query(int s) { LL ans = distv[s]; for(int u = s; fa[u]; u = fa[u]) ans += distv[fa[u]] - distfa[u] + (LL)(val[fa[u]] - val[u]) * cdist(fa[u], s); return ans;}int main() { n = read(); for(int i = 1; i < n; i++) { int a = read(), b = read(), c = read(); AddEdge(a, b, c); } build(1, 0); rmq_init(); f[rt = 0] = size = n; getroot(1, 0); solve(rt);// for(int i = 1; i <= n; i++) printf("%d(%d)%c", fa[i], i, i < n ? ' ' : '\n'); int q = read(); while(q--) { int tp = read(), u = read(); if(tp == 1) { int v = read(); update(u, v); } if(tp == 2) printf("%lld\n", query(u)); } return 0;}