在一片土地上有N个城市，通过N-1条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为1，其中第i个城市的价值为value[i]。
不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。
接下来你需要在线处理M次操作：
0 x k 表示发生了一次地震，震中城市为x，影响范围为k，所有与x距离不超过k的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。
1 x y 表示第x个城市的价值变成了y。
为了体现程序的在线性，操作中的x、y、k都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为0。
第一行包含两个正整数N和M。
第二行包含N个正整数，第i个数表示value[i]。
接下来N-1行，每行包含两个正整数u、v，表示u和v之间有一条无向边。
接下来M行，每行包含三个数，表示M次操作。
包含若干行，对于每个询问输出一行一个正整数表示答案。
动态点分治裸题，考虑一个点向点分子树中的答案统计完以后，还要考虑向父亲距离为某值有多少。
容斥一下，减去父到子的边就好了。
每个节点开一颗权值线段树就好了。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 typedef long long lnt; 5 const int N=100010; 6 struct pnt{ 7 int hd; 8 int fa; 9 int dis; 10 int wgt; 11 int val; 12 int rootp; 13 int roota; 14 int f; 15 int tp; 16 int mxs; 17 bool vis; 18 }p[N]; 19 struct trnt{ 20 int ls; 21 int rs; 22 int val; 23 }tr[10000000]; 24 struct ent{ 25 int twd; 26 int lst; 27 }e[N<<1]; 28 int cnt; 29 int siz; 30 int n,m; 31 int root; 32 int size; 33 int maxsize; 34 int lastans; 35 void ade(int f,int t) 36 { 37 cnt++; 38 e[cnt].twd=t; 39 e[cnt].lst=p[f].hd; 40 p[f].hd=cnt; 41 return ; 42 } 43 void Basic_dfs(int x,int f) 44 { 45 p[x].wgt=1; 46 p[x].f=f; 47 p[x].dis=p[f].dis+1; 48 int maxs=-1; 49 for(int i=p[x].hd;i;i=e[i].lst) 50 { 51 int to=e[i].twd; 52 if(to==f) 53 continue; 54 Basic_dfs(to,x); 55 p[x].wgt+=p[to].wgt; 56 if(p[to].wgt>maxs) 57 { 58 maxs=p[to].wgt; 59 p[x].mxs=to; 60 } 61 } 62 return ; 63 } 64 void Build_dfs(int x,int top) 65 { 66 if(!x) 67 return ; 68 p[x].tp=top; 69 Build_dfs(p[x].mxs,top); 70 for(int i=p[x].hd;i;i=e[i].lst) 71 { 72 int to=e[i].twd; 73 if(to==p[x].f||to==p[x].mxs) 74 continue; 75 Build_dfs(to,to); 76 } 77 return ; 78 } 79 int Lca(int x,int y) 80 { 81 while(p[x].tp!=p[y].tp) 82 { 83 if(p[p[x].tp].dis<p[p[y].tp].dis) 84 x^=y^=x^=y; 85 x=p[p[x].tp].f; 86 } 87 if(p[x].dis>p[y].dis) 88 return y; 89 return x; 90 } 91 int Dis(int x,int y) 92 { 93 int z=Lca(x,y); 94 return p[x].dis+p[y].dis-2*p[z].dis; 95 } 96 void grc_dfs(int x,int f) 97 { 98 p[x].wgt=1; 99 int maxs=-1; 100 for(int i=p[x].hd;i;i=e[i].lst) 101 { 102 int to=e[i].twd; 103 if(to==f||p[to].vis) 104 continue; 105 grc_dfs(to,x); 106 p[x].wgt+=p[to].wgt; 107 if(maxs<p[to].wgt) 108 maxs=p[to].wgt; 109 } 110 maxs=std::max(maxs,size-p[x].wgt); 111 if(maxs<maxsize) 112 { 113 maxsize=maxs; 114 root=x; 115 } 116 return ; 117 } 118 void bin_dfs(int x,int f) 119 { 120 p[x].fa=f; 121 p[x].vis=true; 122 int tmp=size; 123 for(int i=p[x].hd;i;i=e[i].lst) 124 { 125 int to=e[i].twd; 126 if(p[to].vis) 127 continue; 128 root=0; 129 if(p[to].wgt<p[x].wgt) 130 size=p[to].wgt; 131 else 132 size=tmp-p[x].wgt; 133 maxsize=0x3f3f3f3f; 134 grc_dfs(to,to); 135 bin_dfs(root,x); 136 } 137 return ; 138 } 139 void update(int &spc,int l,int r,int pos,int v) 140 { 141 if(!spc) 142 spc=++siz; 143 tr[spc].val+=v; 144 if(l==r) 145 return ; 146 int mid=(l+r)>>1; 147 if(pos<=mid) 148 update(tr[spc].ls,l,mid,pos,v); 149 else 150 update(tr[spc].rs,mid+1,r,pos,v); 151 return ; 152 } 153 void Update(int x,int val) 154 { 155 update(p[x].rootp,0,n-1,0,val); 156 for(int i=x;p[i].fa;i=p[i].fa) 157 { 158 int d=Dis(x,p[i].fa); 159 update(p[p[i].fa].rootp,0,n-1,d,val); 160 update(p[i].roota,0,n-1,d,val); 161 } 162 return ; 163 } 164 int query(int spc,int l,int r,int ll,int rr) 165 { 166 if(!spc) 167 return 0; 168 if(ll>r||l>rr) 169 return 0; 170 if(ll<=l&&r<=rr) 171 return tr[spc].val; 172 int mid=(l+r)>>1; 173 return query(tr[spc].ls,l,mid,ll,rr)+query(tr[spc].rs,mid+1,r,ll,rr); 174 } 175 int Query(int x,int k) 176 { 177 int ans=query(p[x].rootp,0,n-1,0,k); 178 for(int i=x;p[i].fa;i=p[i].fa) 179 { 180 int d=Dis(x,p[i].fa); 181 if(d<=k) 182 ans+=query(p[p[i].fa].rootp,0,n-1,0,k-d)-query(p[i].roota,0,n-1,0,k-d); 183 } 184 return ans; 185 } 186 int main() 187 { 188 scanf("%d%d",&n,&m); 189 for(int i=1;i<=n;i++) 190 scanf("%d",&p[i].val); 191 for(int i=1;i<n;i++) 192 { 193 int a,b; 194 scanf("%d%d",&a,&b); 195 ade(a,b); 196 ade(b,a); 197 } 198 Basic_dfs(1,1); 199 Build_dfs(1,1); 200 root=0; 201 size=n; 202 maxsize=0x3f3f3f3f; 203 204 grc_dfs(1,1); 205 bin_dfs(root,0); 206 for(int i=1;i<=n;i++) 207 Update(i,p[i].val); 208 while(m--) 209 { 210 int cmd; 211 scanf("%d",&cmd); 212 if(cmd==0) 213 { 214 int a,b; 215 scanf("%d%d",&a,&b); 216 a^=lastans; 217 b^=lastans; 218 lastans=Query(a,b); 219 printf("%d\n",lastans); 220 }else{ 221 int a,b; 222 scanf("%d%d",&a,&b); 223 a^=lastans; 224 b^=lastans; 225 Update(a,b-p[a].val); 226 p[a].val=b; 227 } 228 } 229 return 0; 230 }
原文：https://www.cnblogs.com/blog-Dr-J/p/10159886.html