题目描述
给一颗n个节点的树，边权均为1，初始点权均为0，m次操作：
Q x：询问x的点权。
M x d w：将树上与节点x距离不超过d的节点的点权均加上w。
输入
第一行两个正整数：n，m
接下来的n-1行，每行三个正整数u，v，代表u，v之间有一条边。
接下来的m行，每行给出上述两种操作中的一种。
输出
对于每个Q操作，输出当前x节点的皮皮鼠数量。
样例输入
7 6
1 2
1 4
1 5
2 3
2 7
5 6
M 1 1 2
Q 5
M 2 2 3
Q 3
M 1 2 1
Q 2
样例输出
2
3
6
题解
动态点分治+线段树
看到距离一眼动态点分治。考虑单次修改对哪些点产生贡献：对于 $x$ 和它在点分树上距离为 $l$ 的祖先 $y$ ，如果 $l\le d$ ，则在 $y$ 子树中与 $y$ 距离不超过 $d-l$ 的点会得到 $x$ 的贡献。
因此对于每个点开一棵线段树，维护点分树内与它的距离中哪些受到了影响。查询时直接从 $x$ 向根移动，过程中查询在每个点处的贡献。其中需要容斥一下。
需要完成：前缀修改、单点查询，可以差分后转变为：单点修改、后缀查询。使用线段树维护。
时间复杂度 $O(n\log^2n)$
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;
int head[N] , to[N << 1] , next[N << 1] , cnt , deep[N] , pos[N] , val[N << 1][18] , log[N << 1] , tot;
int ls[N << 7] , rs[N << 7] , sum[N << 7] , tp , ra[N] , rb[N];
int n , si[N] , ms[N] , ts , root , fa[N] , vis[N];
char str[5];
inline void add(int x , int y)
{
to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;
}
void dfs(int x , int pre)
{
int i;
pos[x] = ++tot , val[tot][0] = deep[x];
for(i = head[x] ; i ; i = next[i])
if(to[i] != pre)
deep[to[i]] = deep[x] + 1 , dfs(to[i] , x) , val[++tot][0] = deep[x];
}
inline int dis(int x , int y)
{
int tx = pos[x] , ty = pos[y] , k;
if(tx > ty) swap(tx , ty);
k = log[ty - tx + 1];
return deep[x] + deep[y] - (min(val[tx][k] , val[ty - (1 << k) + 1][k]) << 1);
}
void update(int p , int a , int l , int r , int &x)
{
if(!x) x = ++tp;
sum[x] += a;
if(l == r) return;
int mid = (l + r) >> 1;
if(p <= mid) update(p , a , l , mid , ls[x]);
else update(p , a , mid + 1 , r , rs[x]);
}
int query(int p , int l , int r , int x)
{
if(l == r) return sum[x];
int mid = (l + r) >> 1;
if(p <= mid) return query(p , l , mid , ls[x]) + sum[rs[x]];
else return query(p , mid + 1 , r , rs[x]);
}
void getroot(int x , int pre)
{
int i;
si[x] = 1 , ms[x] = 0;
for(i = head[x] ; i ; i = next[i])
if(!vis[to[i]] && to[i] != pre)
getroot(to[i] , x) , si[x] += si[to[i]] , ms[x] = max(ms[x] , si[to[i]]);
ms[x] = max(ms[x] , ts - si[x]);
if(ms[x] < ms[root]) root = x;
}
void divide(int x)
{
int i;
vis[x] = 1;
for(i = head[x] ; i ; i = next[i])
if(!vis[to[i]])
ts = si[to[i]] , root = 0 , getroot(to[i] , 0) , fa[root] = x , divide(root);
}
void modify(int x , int d , int w)
{
int i , t;
for(i = x ; i ; i = fa[i])
if(d >= (t = dis(x , i)))
update(d - t , w , 0 , n , ra[i]);
for(i = x ; fa[i] ; i = fa[i])
if(d >= (t = dis(x , fa[i])))
update(d - t , w , 0 , n , rb[i]);
}
int solve(int x)
{
int i , ans = 0;
for(i = x ; i ; i = fa[i]) ans += query(dis(x , i) , 0 , n , ra[i]);
for(i = x ; fa[i] ; i = fa[i]) ans -= query(dis(x , fa[i]) , 0 , n , rb[i]);
return ans;
}
int main()
{
int m , i , j , x , y , z;
scanf("%d%d" , &n , &m);
for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);
dfs(1 , 0);
for(i = 2 ; i <= tot ; i ++ ) log[i] = log[i >> 1] + 1;
for(i = 1 ; (1 << i) <= tot ; i ++ )
for(j = 1 ; j <= tot - (1 << i) + 1 ; j ++ )
val[j][i] = min(val[j][i - 1] , val[j + (1 << (i - 1))][i - 1]);
ms[0] = 1 << 30 , ts = n , getroot(1 , 0) , divide(root);
while(m -- )
{
scanf("%s%d" , str , &x);
if(str[0] == 'M') scanf("%d%d" , &y , &z) , modify(x , y , z);
else printf("%d\n" , solve(x));
}
return 0;
}
