[题目描述]
在一片土地上有 $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$ 次操作.
[输出格式]
包含若干行, 对于每个询问输出一行一个正整数表示答案.
[样例输入]
- 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
[样例输出]
11100101
[数据范围与提示]
- $1 \le N,M \le 100000$
- $1 \le u,v,x \le N $
- $1 \le value[i],y \le 10000 $
- $ 0 \le k \le N-1 $
题解
要求树上和一个点距离不超过 $k$ 的所有点, 很容易想到动态点分治
开 $ n $ 棵权值线段树, 记录当前点分中心距离为 $ v $ 的点的个数
考虑在点分树上查询, 会发现在 $ x $ 统计过答案的点有可能在 $ fa[x] $ 上也被统计
考虑容斥, 再开 $ n $ 棵线段树, 记录从当前点分中心 $ x $ 经过 $ fa[x] $ 距离为 $ v $ 的权值和, 查询时扣掉即可
时间效率:$ O(nlog^2 n) $
代码
- #include<bits/stdc++.h>
- #define LL long long
- #define il inline
- #define re register
- #define _(d) while(d(isdigit(ch=getchar())))
- using namespace std;
- il int R(){
- int x;bool f=1;char ch;_(!)if(ch=='-')f=0;x=ch^48;
- _()x=(x<<3)+(x<<1)+(ch^48);return f?x:-x;}
- const int N=2e5+10;
- int n,m,ans,f[N],top[N],dep[N],sz[N],son[N],head[N],cnt,Mx,Rt,Sz,fa[N],siz[N],val[N],rot[N<<1],tot;
- bool vis[N];
- struct seg{int ls,rs,v;}tr[N<<6];
- struct edge{int to,nex;}e[N<<1];
- il void add(int s,int t){e[++cnt]=(edge){t,head[s]},head[s]=cnt;}
- il void dfs(int x,int far){
- f[x]=far,sz[x]=1,dep[x]=dep[far]+1;
- for(re int v,k=head[x];k;k=e[k].nex)
- if((v=e[k].to)!=far){
- dfs(v,x),sz[x]+=sz[v];
- if(sz[v]>sz[son[x]])son[x]=v;
- }
- return;
- }
- il void DFS(int x,int far){
- top[x]=far;
- if(son[x])DFS(son[x],far);
- for(re int k=head[x],v;k;k=e[k].nex)
- if((v=e[k].to)!=f[x]&&v!=son[x])
- DFS(v,v);
- }
- il int lca(int x,int y){
- while(top[x]^top[y]){
- if(dep[top[x]]<dep[top[y]])swap(x,y);
- x=f[top[x]];
- }
- return dep[x]<dep[y]?x:y;
- }
- il int get(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
- il void getrot(int u,int far){
- int mx=0;siz[u]=1;
- for(re int k=head[u],v;k;k=e[k].nex)
- if((v=e[k].to)!=far&&!vis[v])
- getrot(v,u),siz[u]+=siz[v],mx=max(mx,siz[v]);
- mx=max(mx,Sz-siz[u]);
- if(mx<Mx)Mx=mx,Rt=u;
- return;
- }
- il int getsize(int u,int far){
- siz[u]=1;
- for(re int k=head[u],v;k;k=e[k].nex)
- if((v=e[k].to)!=far&&!vis[v])
- siz[u]+=getsize(v,u);
- return siz[u];
- }
- void slove(int u,int far){
- Mx=1e9,getrot(u,0),vis[Rt]=1;
- fa[Rt]=far,far=Rt;
- for(re int k=head[Rt],v;k;k=e[k].nex)
- if(!vis[v=e[k].to])Sz=getsize(v,0),slove(v,far);
- }
- #define Ls tr[rt].ls
- #define Rs tr[rt].rs
- il void change(int &rt,int l,int r,int k,int x){
- if(!rt)rt=++tot;
- tr[rt].v+=x;
- if(l==r)return;
- int mid=(l+r)>>1;
- if(k<=mid)change(Ls,l,mid,k,x);
- else change(Rs,mid+1,r,k,x);
- return;
- }
- il int query(int rt,int l,int r,int qr){
- if(!rt)return 0;
- if(qr>=r)return tr[rt].v;
- int mid=(l+r)>>1,res=0;
- if(qr>mid)res=tr[Ls].v+query(Rs,mid+1,r,qr);
- else res=query(Ls,l,mid,qr);
- return res;
- }
- il void update(int x,int v){
- change(rot[x],0,n,0,v);
- for(re int i=x;fa[i];i=fa[i]){
- int dis=get(x,fa[i]);
- change(rot[fa[i]],0,n,dis,v);
- change(rot[i+n],0,n,dis,v);
- }
- }
- il int ask(int x,int y){
- int res=query(rot[x],0,n,y);
- for(re int i=x;fa[i];i=fa[i]){
- int dis=get(x,fa[i]);
- if(dis>y)continue;
- res+=query(rot[fa[i]],0,n,y-dis)-query(rot[i+n],0,n,y-dis);
- }
- return res;
- }
- int main(){
- n=R(),m=R();
- for(re int i=1;i<=n;i++)val[i]=R();
- for(re int i=1,u,v;i<n;i++)
- u=R(),v=R(),add(u,v),add(v,u);
- dfs(1,0),DFS(1,1),Sz=n,slove(1,0);
- for(re int i=1;i<=n;i++)update(i,val[i]);
- for(re int i=1;i<=m;i++){
- int op=R(),x=R()^ans,y=R()^ans;
- if(op)update(x,y-val[x]),val[x]=y;
- else printf("%d\n",ans=ask(x,y));
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3013240.html