题意：
一棵树，每个点有点权w，q次操作
1.将点x的点权修改为y
2.问离x距离不超过d的点权和
思路：
将树分治中的计算部分需要的树状数组提出来，维护这个树状数组，每次查询修改均为O（log2n）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | #include<bits/stdc++.h>using namespace std;const int N=100005;vector<int>link[N];struct MSG{ int id1,id2; int deep;}msg[N][17];int w[N];int c[N*17];int idn,L[N*2],R[N*2];int maxfloor[N];void add(int l,int r,int x,int y){ for (int i=x;i<r-l;i+=(i&-i)) c[l+i]+=y;}int get(int l,int r,int x){ if (x<1) return 0; if (x>=r-l) x=r-l-1; int ret=0; for (int i=x;i;i-=(i&-i)) ret+=c[l+i]; return ret;}bool vis[N];int cent,mxsz;int size[N];void findcent(int u,int fa,int n){ size[u]=1; int mx=0; for (int v:link[u]) { if (vis[v]||v==fa) continue; findcent(v,u,n); size[u]+=size[v]; mx=max(mx,size[v]); } mx=max(mx,n-size[u]); if (mx<mxsz) cent=u,mxsz=mx;}int getmaxdeep(int u,int fa){ int ret=1; for (int v:link[u]) if (v!=fa&&!vis[v]) ret=max(ret,1+getmaxdeep(v,u)); return ret;}void dfs(int u,int fa,int deep,int idn,int floor,int tp){ if (tp==0) msg[u][floor].id1=idn; else msg[u][floor].id2=idn; msg[u][floor].deep=deep; add(L[idn],R[idn],deep,w[u]); for (int v:link[u]) if (!vis[v]&&v!=fa) dfs(v,u,deep+1,idn,floor,tp);}void build(int u,int n,int floor){ cent=u; mxsz=n; findcent(u,-1,n); u=cent; maxfloor[u]=floor; idn++; L[idn]=R[idn-1]; R[idn]=L[idn]+getmaxdeep(u,-1)+1; dfs(u,-1,1,idn,floor,0); msg[u][floor].id2=-1; for (int v:link[u]) if (!vis[v]) { idn++; L[idn]=R[idn-1]; R[idn]=L[idn]+getmaxdeep(v,u)+2; dfs(v,u,2,idn,floor,1); } vis[u]=1; for (int v:link[u]) if (!vis[v]) if (size[v]<size[u]) build(v,size[v],floor+1); else build(v,n-size[u],floor+1);}int main(){ int n,q; while(~scanf("%d%d",&n,&q)) { for (int i=1;i<=n;i++) scanf("%d",&w[i]); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); link[x].push_back(y); link[y].push_back(x); } build(1,n,0); while(q--) { char s[2]; int x,y; scanf("%s%d%d",s,&x,&y); if (s[0]=='?') { int ans=0; for (int floor=0;floor<=maxfloor[x];floor++) { int id1=msg[x][floor].id1; int id2=msg[x][floor].id2; int deep=msg[x][floor].deep; ans+=get(L[id1],R[id1],y+2-deep); if (id2!=-1) ans-=get(L[id2],R[id2],y+2-deep); } printf("%d\n",ans); } else { for (int floor=0;floor<=maxfloor[x];floor++) { int id1=msg[x][floor].id1; int id2=msg[x][floor].id2; int deep=msg[x][floor].deep; add(L[id1],R[id1],deep,y-w[x]); if (id2!=-1) add(L[id2],R[id2],deep,y-w[x]); } w[x]=y; } } memset(vis,0,sizeof(vis)); memset(msg,0,sizeof(msg)); memset(w,0,sizeof(w)); memset(c,0,sizeof(c)); idn=0; for (int i=1;i<=n;i++) link[i].clear(); }} |
