烁烁的游戏 题目大意：
给你一棵$n$个节点的树，有$m$次操作，询问某个节点的权值，或者将与某个点$x$距离不超过$d$的所有节点的权值都增加$w$
动态点分裸题
每个节点开一棵权值线段树
对于修改操作，它从$x$开始，像一个涟漪扩散，对它周围与它距离$leq d$的所有节点造成$w$点贡献
为了记录这个操作的贡献，我们寻找树分治每一层中 包含这个节点的那个点分树的重心$root$
在$root$处记录贡献，开一棵动态开点权值线段树，记录与这个节点距离为$d$的贡献总和，显然在$root$周围扩散范围是$d-dis(x,root)$
还要去掉包含$x$子树的贡献，所以每个节点要再开一个，记录对于父重心需要去掉的贡献
每次查询都沿着点分重心往上跳，因为修改的过程是在线段树上打差分，所以在当前重心查询$d-dis(x,root)$的后缀和即可
由于每次修改都要不断网上跳重心，一共要修改$log$次，每次都要求距离，所以采用欧拉序求$LCA$减小常数
空间是$O(nlog^{2}n)$的，容易被卡，记录当前节点最大能扩散的范围，即当前节点接管的那部分子树内节点的最大深度，非常有效地优化了空间
实在是讲不太明白，大家可以看代码
1 #include <map> 2 #include <queue> 3 #include <vector> 4 #include <cstdio> 5 #include <cstring> 6 #include <algorithm> 7 #define N1 101000 8 #define ll long long 9 #define dd double 10 #define inf 0x3f3f3f3f3f3f3f3fll 11 using namespace std; 12 13 int gint() 14 { 15 int ret=0,fh=1;char c=getchar(); 16 while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();} 17 while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();} 18 return ret*fh; 19 } 20 21 struct SEG{ 22 int sum[N1*150],ls[N1*150],rs[N1*150],rm[N1],rf[N1],tot; 23 void pushup(int rt){sum[rt]=sum[ls[rt]]+sum[rs[rt]];} 24 void update(int x,int l,int r,int &rt,int w) 25 { 26 if(!rt) rt=++tot; 27 if(l==r) {sum[rt]+=w;return;} 28 int mid=(l+r)>>1; 29 if(x<=mid) update(x,l,mid,ls[rt],w); 30 else update(x,mid+1,r,rs[rt],w); 31 pushup(rt); 32 } 33 int query(int L,int R,int l,int r,int rt) 34 { 35 if(!rt) return 0; 36 if(L<=l&&r<=R) return sum[rt]; 37 int mid=(l+r)>>1,ans=0; 38 if(L<=mid) ans+=query(L,R,l,mid,ls[rt]); 39 if(R>mid) ans+=query(L,R,mid+1,r,rs[rt]); 40 return ans; 41 } 42 }s; 43 44 struct Edge{ 45 int to[N1<<1],nxt[N1<<1],head[N1],cte; 46 void ae(int u,int v) 47 {cte++;to[cte]=v,nxt[cte]=head[u],head[u]=cte;} 48 }e; 49 50 int n,m,T; 51 namespace tr{ 52 int dep[N1],ff[N1<<1][20],st[N1],id[N1<<1],lg[N1<<1],tot; 53 void dfs1(int u,int dad) 54 { 55 id[++tot]=u; st[u]=tot; ff[tot][0]=u; 56 for(int j=e.head[u];j;j=e.nxt[j]) 57 { 58 int v=e.to[j]; if(v==dad) continue; 59 dep[v]=dep[u]+1; dfs1(v,u); id[++tot]=u; ff[tot][0]=u; 60 } 61 } 62 void get_st() 63 { 64 int i,j; 65 for(lg[1]=0,i=2;i<=tot;i++) lg[i]=lg[i>>1]+1; 66 for(j=1;j<=lg[tot];j++) 67 for(i=1;i+(1<<j)-1<=tot;i++) 68 ff[i][j]=dep[ ff[i][j-1] ]<dep[ ff[i+(1<<(j-1))][j-1] ]?ff[i][j-1]:ff[i+(1<<(j-1))][j-1]; 69 } 70 int dis(int x,int y) 71 { 72 int tx=min(st[x],st[y]),ty=max(st[x],st[y]),L=ty-tx+1; 73 int fa=dep[ ff[tx][lg[L]] ]<dep[ ff[ty-(1<<lg[L])+1][lg[L]] ]?ff[tx][lg[L]]:ff[ty-(1<<lg[L])+1][lg[L]]; 74 return dep[x]+dep[y]-2*dep[fa]; 75 } 76 void init(){dfs1(1,-1);get_st();} 77 }; 78 79 using tr::dis; 80 81 int ms[N1],sz[N1],dep[N1],mad[N1],use[N1],fa[N1],tsz,G; 82 void dfs(int u,int dad,int g) 83 { 84 mad[g]=max(mad[g],dep[u]); sz[u]=1; 85 for(int j=e.head[u];j;j=e.nxt[j]) 86 { 87 int v=e.to[j]; if(v==dad||use[v]) continue; 88 dep[v]=dep[u]+1; dfs(v,u,g); sz[u]+=sz[v]; 89 } 90 } 91 void gra(int u,int dad) 92 { 93 sz[u]=1; ms[u]=0; 94 for(int j=e.head[u];j;j=e.nxt[j]) 95 { 96 int v=e.to[j]; if(use[v]||v==dad) continue; 97 gra(v,u); sz[u]+=sz[v]; ms[u]=max(ms[u],sz[v]); 98 } 99 ms[u]=max(ms[u],tsz-sz[u]); 100 if(ms[u]<ms[G]) G=u; 101 } 102 void main_dfs(int u) 103 { 104 use[u]=1; dep[u]=0; dfs(u,-1,u); 105 for(int j=e.head[u];j;j=e.nxt[j]) 106 { 107 int v=e.to[j]; if(use[v]) continue; 108 G=0; tsz=sz[v]; gra(v,-1); fa[G]=u; 109 main_dfs(G); 110 } 111 } 112 void modify(int x,int K,int w) 113 { 114 int i,D; 115 for(i=x;i;i=fa[i]) 116 { 117 D=dis(x,i); 118 if(D<=K) s.update(min(mad[i],K-D),0,mad[i],s.rm[i],w); 119 if(!fa[i]) break; 120 D=dis(x,fa[i]); 121 if(D<=K) s.update(min(mad[fa[i]],K-D),0,mad[fa[i]],s.rf[i],w); 122 } 123 } 124 int query(int x) 125 { 126 int i,D,ans=0; 127 for(i=x;i;i=fa[i]) 128 { 129 D=dis(x,i); 130 if(D<=mad[i]) ans+=s.query(D,mad[i],0,mad[i],s.rm[i]); 131 if(!fa[i]) break; 132 D=dis(x,fa[i]); 133 if(D<=mad[fa[i]]) ans-=s.query(D,mad[fa[i]],0,mad[fa[i]],s.rf[i]); 134 } 135 return ans; 136 } 137 138 int main() 139 { 140 scanf("%d%d",&n,&m); 141 int i,j,x,y,w,ans=0; 142 for(i=1;i<n;i++) x=gint(), y=gint(), e.ae(x,y), e.ae(y,x); 143 tr::init(); 144 ms[0]=tsz=n; G=0; gra(1,-1); gra(G,-1); 145 main_dfs(G); char str[10]; 146 for(i=1;i<=m;i++) 147 { 148 scanf("%s",str); 149 if(str[0]=='M'){ 150 x=gint(); y=gint(); w=gint(); 151 modify(x,y,w); 152 }else{ 153 x=gint(); 154 ans=query(x); 155 printf("%d ",ans); 156 } 157 } 158 return 0; 159 }
震波那道题和这道题非常像，只不过是点的修改和子树的查询
但由于我一直被卡常，没脸放代码了qwq