[文章目录]
Description
给一颗n个节点的树，边权均为1，初始点权均为0，m次操作：
Q x：询问x的点权。
M x d w：将树上与节点x距离不超过d的节点的点权均加上w。n，m<=10^5,|w|<=10^4
动态点分治，对于每个块线段树维护到根的距离对应累加的w的和，以及到该点分治的父亲节点的距离对应累加的w的和【用于容斥】。
复杂度nlog^2n
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
const int inf=0x3f3f3f3f;
int n,m,head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
int mi[N<<1][20],Log[N<<1],dep[N],pos[N],tim;
void dfs(int x,int pre)
{
dep[x]=dep[pre]+1; pos[x]=++tim; mi[tim][0]=dep[x];
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
dfs(to[i],x),mi[++tim][0]=dep[x];
}
int dis(int x,int y)
{
if(pos[x]>pos[y]) swap(x,y);
int lo=Log[pos[y]-pos[x]+1];
return dep[x]+dep[y]-(min(mi[pos[x]][lo],mi[pos[y]-(1<<lo)+1][lo])<<1);
}
struct seg
{
int ls,rs,s;
}t[N*400];
int se,r1[N],r2[N];
void insert(int &r1,int r2,int l,int r,int x,int y)
{
if(!r1) r1=++se; t[r1].s=t[r2].s+y;
if(l==r) return ; int mid=(l+r)>>1;
if(x<=mid) insert(t[r1].ls,t[r2].ls,l,mid,x,y);
else insert(t[r1].rs,t[r2].rs,mid+1,r,x,y);
}
int query(int r1,int l,int r,int x)
{
if(!r1) return 0;
if(x<=l) return t[r1].s;
int mid=(l+r)>>1;
if(x<=mid) return t[t[r1].rs].s+query(t[r1].ls,l,mid,x);
else return query(t[r1].rs,mid+1,r,x);
}
int root,nn,siz[N],msi[N],fa[N];
bool vis[N];
void getroot(int x,int pre)
{
siz[x]=1; msi[x]=0;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)
getroot(to[i],x),siz[x]+=siz[to[i]],msi[x]=max(msi[x],siz[to[i]]);
msi[x]=max(msi[x],nn-siz[x]);
if(msi[x]<msi[root]) root=x;
}
void Dfs(int x,int pre)
{
siz[x]=1;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)
Dfs(to[i],x),siz[x]+=siz[to[i]];
}
void build(int x,int pre)
{
fa[x]=pre; vis[x]=1; Dfs(x,0);
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]])
{
nn=siz[to[i]]; root=0;
getroot(to[i],x); build(root,x);
}
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,x,y;
for(i=1;i<n;++i) scanf("%d%d",&x,&y),add(x,y);
dfs(1,0);
for(i=2;i<=tim;++i) Log[i]=Log[i>>1]+1;
for(i=1;i<=Log[tim];++i) for(j=1;j+(1<<i)-1<=tim;++j)
mi[j][i]=min(mi[j][i-1],mi[j+(1<<(i-1))][i-1]);
nn=n; root=0; msi[0]=inf;
getroot(1,0); build(root,0);
char op[10]; int d,w,ans;
while(m--)
{
scanf("%s",op);
if(op[0]=='Q')
{
scanf("%d",&x);
for(ans=0,i=x;i;i=fa[i])
{
ans+=query(r1[i],0,n,dis(x,i));
if(fa[i]) ans+=query(r2[i],0,n,dis(x,fa[i]));
}
printf("%d\n",ans);
}
else
{
scanf("%d%d%d",&x,&d,&w);
for(i=x;i;i=fa[i])
{
if(d>=dis(x,i)) insert(r1[i],r1[i],0,n,d-dis(x,i),w);
if(fa[i]&&d>=dis(x,fa[i])) insert(r2[i],r2[i],0,n,d-dis(x,fa[i]),-w);
}
}
}
return 0;
}