Description：

一棵 $n$ 个节点的树， $m$ 次操作： $Q$ $x$ ：询问 $x$ 的点权。 $M$ $x$ $d$ $w$ ：将树上与节点 $x$ 距离不超过 $d$ 的节点的点权均加上 $w$ 。

$1\leqslant n\leqslant 10^5$

Solution：

肯定是动态点分治，首先像所有动态点分治一样记一个 $sum$ 一个 $tofa$ ，像震波那题一样这两个分别以距离为下标开两棵线段树，之前不理解为什么这么做是对的，因为动态点分治构建点分树这个操作保证了在每个子树内都是沿着最短路径走的，所以修改就是在每个线段树上 $[0,d-dist_{k,i}]$ 区间加，查询就是在线段树上查 $dist_{k,i}$ 这个位置的值，需要标记永久化。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline char getc()

{

	register char c = getchar();

	while(c != 'M' && c != 'Q')c = getchar();

	return c;

}

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 100010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

struct node

{

	int lc,rc;

	int tag;

	node(){tag = 0;}

}t[MAXN * 200];

int ptr = 0;

int newnode(){return ++ptr;}

int sum[MAXN],tofa[MAXN];

#define mid ((l + r) >> 1)

void insert(int &rt,int L,int R,int k,int l,int r)

{

	if(L > R)return;

	if(rt == 0)rt = newnode();

	if(L <= l && r <= R)

	{

		t[rt].tag += k;

		return;

	}

	if(L <= mid)insert(t[rt].lc,L,R,k,l,mid);

	if(R > mid)insert(t[rt].rc,L,R,k,mid + 1,r);

	return;

}

int query(int rt,int p,int l,int r)

{

	if(rt == 0)return 0;

	if(l == r)return t[rt].tag;

	int res = 0;

	if(p <= mid)res = query(t[rt].lc,p,l,mid);

	else res = query(t[rt].rc,p,mid + 1,r);

	res += t[rt].tag;

	return res;

}

int size[MAXN],d[MAXN],root,s,anc[MAXN];

#define INF 0x3f3f3f3f

bool vis[MAXN];

void getroot(int k,int fa)

{

	size[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to] || e[i].to == fa)continue;

		getroot(e[i].to,k);

		size[k] += size[e[i].to];

		d[k] = max(d[k],size[e[i].to]);

	}

	d[k] = max(d[k],s - size[k]);

	if(d[k] < d[root])root = k;

	return;

}

void divide(int k)

{

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		root = 0;s = size[e[i].to];

		getroot(e[i].to,0);

		anc[root] = k;

		divide(root);

	}

	return;

}

int fa[MAXN],siz[MAXN],top[MAXN],dep[MAXN],son[MAXN];

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

int dis(int a,int b)

{

	return dep[a] + dep[b] - 2 * dep[LCA(a,b)];

}

void modify(int k,int d,int x)

{

	insert(sum[k],0,d,x,0,n);

	for(int i = k;anc[i] != 0;i = anc[i])

	{

		int dist = dis(k,anc[i]);

		insert(tofa[i],0,d - dist,x,0,n);

		insert(sum[anc[i]],0,d - dist,x,0,n);

	}

	return;

}

int calc(int k)

{

	int ans = query(sum[k],0,0,n);

	for(int i = k;anc[i] != 0;i = anc[i])

	{

		int dist = dis(k,anc[i]);

		ans += query(sum[anc[i]],dist,0,n) - query(tofa[i],dist,0,n);

	}

	return ans;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i < n;++i)add(rd(),rd());

	root = 0;s = n;d[0] = INF;

	getroot(1,0);

	divide(root);

	dfs1(1,1);dfs2(1,1);

	char c;int k,d,x;

	for(int i = 1;i <= m;++i)

	{

		c = getc();

		if(c == 'Q')

		{

			k = rd();

			printf("%d\n",calc(k));

		}

		else

		{

			k = rd();d = rd();x = rd();

			modify(k,d,x);

		}

	}

	return 0;

}