题面戳我
题意：
给一颗n个节点的树，边权均为1，初始点权均为0，m次操作：
Q x：询问x的点权。
M x d w：将树上与节点x距离不超过d的节点的点权均加上w。
\(1≤n≤10^5\)
sol
和前一题是一样的[BZOJ3730]震波
这里是线段树的区间修改+单点查询。标记永久化就很舒服（不用pushup和pushdown）
code
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100005;
int gi()
{
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
struct edge{int to,next;}a[N<<1];
int n,m,head[N],cnt,pa[N],dep[N],sz[N],son[N],top[N];
int root,sum,w[N],vis[N],fa[N],rt[N<<1],tot;
struct segment_tree{int ls,rs,v;}t[N*300];
void dfs1(int u,int f)
{
pa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
for (int e=head[u];e;e=a[e].next)
{
int v=a[e].to;if (v==f) continue;
dfs1(v,u);
sz[u]+=sz[v];if (sz[v]>sz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int up)
{
top[u]=up;
if (son[u]) dfs2(son[u],up);
for (int e=head[u];e;e=a[e].next)
if (a[e].to!=pa[u]&&a[e].to!=son[u])
dfs2(a[e].to,a[e].to);
}
int lca(int u,int v)
{
while (top[u]^top[v])
{
if (dep[top[u]]<dep[top[v]]) swap(u,v);
u=pa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
int getdis(int u,int v){return dep[u]+dep[v]-(dep[lca(u,v)]<<1);}
void getroot(int u,int f)
{
sz[u]=1;w[u]=0;
for (int e=head[u];e;e=a[e].next)
{
int v=a[e].to;if (v==f||vis[v]) continue;
getroot(v,u);
sz[u]+=sz[v];w[u]=max(w[u],sz[v]);
}
w[u]=max(w[u],sum-sz[u]);
if (w[u]<w[root]) root=u;
}
void solve(int u,int f)
{
fa[u]=f;vis[u]=1;int pre_sum=sum;
for (int e=head[u];e;e=a[e].next)
{
int v=a[e].to;if (vis[v]) continue;
if (sz[v]>sz[u]) sum=pre_sum-sz[u];
else sum=sz[v];
root=0;
getroot(v,0);
solve(root,u);
}
}
void Modify(int &x,int l,int r,int ql,int qr,int v)
{
if (!x) x=++tot;
if (l>=ql&&r<=qr) {t[x].v+=v;return;}
int mid=l+r>>1;
if (ql<=mid) Modify(t[x].ls,l,mid,ql,qr,v);
if (qr>mid) Modify(t[x].rs,mid+1,r,ql,qr,v);
}
int Query(int x,int l,int r,int pos)
{
if (!x) return 0;
if (l==r) return t[x].v;
int mid=l+r>>1;
if (pos<=mid) return t[x].v+Query(t[x].ls,l,mid,pos);
else return t[x].v+Query(t[x].rs,mid+1,r,pos);
}
void PreModify()
{
int u=gi(),d=gi(),v=gi();
Modify(rt[u],0,n-1,0,d,v);
for (int i=u;fa[i];i=fa[i])
{
int dist=getdis(u,fa[i]);
if (d>=dist) Modify(rt[fa[i]],0,n-1,0,d-dist,v),Modify(rt[i+n],0,n-1,0,d-dist,v);
}
}
int PreQuery()
{
int u=gi(),res=Query(rt[u],0,n-1,0);
for (int i=u;fa[i];i=fa[i])
{
int dist=getdis(u,fa[i]);
res+=Query(rt[fa[i]],0,n-1,dist)-Query(rt[i+n],0,n-1,dist);
}
return res;
}
int main()
{
n=gi();m=gi();
for (int i=1;i<n;i++)
{
int u=gi(),v=gi();
a[++cnt]=(edge){v,head[u]};head[u]=cnt;
a[++cnt]=(edge){u,head[v]};head[v]=cnt;
}
dfs1(1,0);dfs2(1,1);
sum=w[0]=n;
getroot(1,0);
solve(root,0);
while (m--)
{
char ch=getchar();
while (ch!='Q'&&ch!='M') ch=getchar();
if (ch=='Q') printf("%d\n",PreQuery());
else PreModify();
}
return 0;
}