BZOJ3730: 震波(动态点分治)

Description

在一片土地上有N个城市，通过N-1条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为1，其中第i个城市的价值为value[i]。
不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。
接下来你需要在线处理M次操作：
0 x k 表示发生了一次地震，震中城市为x，影响范围为k，所有与x距离不超过k的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。
1 x y 表示第x个城市的价值变成了y。
为了体现程序的在线性，操作中的x、y、k都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为0。

Input

第一行包含两个正整数N和M。
第二行包含N个正整数，第i个数表示value[i]。
接下来N-1行，每行包含两个正整数u、v，表示u和v之间有一条无向边。
接下来M行，每行包含三个数，表示M次操作。

Output

包含若干行，对于每个询问输出一行一个正整数表示答案。

Sample Input

8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1

解题思路：

动态点分治裸题，考虑一个点向点分子树中的答案统计完以后，还要考虑向父亲距离为某值有多少。

容斥一下，减去父到子的边就好了。

每个节点开一颗权值线段树就好了。

代码：

  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
",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 }