蒟蒻救助 树剖模板

#include <algorithm>
#include <cstdio>
#define N 100010
#define ll long long
using namespace std;
inline int re() {
	int x = 0; char q = getchar();
	while (q < '0' || q > '9') q = getchar();
	while ('0' <= q && q <= '9') x = x * 10 + q - 48,q = getchar();
	return x;
}
inline int rd() {
	char q = getchar();
	while (q != 'A' && q != 'Q') q = getchar();
	return q == 'A';
}
struct edge{int ne,to;}e[N << 1];
int dep[N],siz[N],son[N],top[N],fa[N],id[N];
int first[N],tot,n = re();
ll laz[N << 3],tr[N << 3];
inline void add(int x,int y) {
	e[++tot].ne = first[x],e[tot].to = y,first[x] = tot;
	e[++tot].ne = first[y],e[tot].to = x,first[y] = tot;
}
inline void dfs1(int p) {
	dep[p] = dep[fa[p]] + 1,++siz[p];
	for (int a = first[p],b = e[a].to ; a ; a = e[a].ne,b = e[a].to)
	if (b == fa[p]) continue; else {
		fa[b] = p,dfs1(b);siz[p] += siz[b];
		if (siz[son[p]] < siz[b]) son[p] = b;
	}
}
inline void dfs2(int p,int f) {
	id[p] = ++tot,top[p] = f;
	if (!son[p]) return; dfs2(son[p],f);
	for (int a = first[p],b = e[a].to ; a ; a = e[a].ne,b = e[a].to)
	if (b != fa[p] && b != son[p]) dfs2(b,b);
}
inline void update(int l,int r,int len,int i,int j,int w) {
	if (laz[len]) pushdown(l,r,len);
	if (i <= l && r <= j) {tr[len] += (r - l + 1) * w,laz[len] += w; return;}
	int mid = (l + r) >> 1;
	if (i <= mid) update(l,mid,len << 1,i,j,w);
	if (mid < j) update(mid + 1,r,len << 1 | 1,i,j,w);
	tr[len] = tr[len << 1] + tr[len << 1 | 1];
}
inline void pushdown(int l,int r,int len) {
	laz[len << 1] += laz[len];
	laz[len << 1 | 1] += laz[len];
	int mid = (l + r) >> 1;
	tr[len << 1] += laz[len] * (mid - l + 1);
	tr[len << 1 | 1] += laz[len] * (r - mid);
	laz[len] = 0;
}
inline ll get(int l,int r,int len,int i,int j) {
	if (laz[len]) pushdown(l,r,len);
	if (i <= l && r <= j) return tr[len];
	int mid = (l + r) >> 1; ll bot = 0;
	if (i <= mid) bot = get(l,mid,len << 1,i,j);
	if (mid < j) bot += get(mid + 1,r,len << 1 | 1,i,j);
	return bot;
}
inline ll out(int x,int y) {
	ll ans = 0;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x,y);
		ans += get(1,n,1,id[top[x]],id[x]);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x,y);
	return get(1,n,1,id[x],id[y]) + ans;
}
int main() {
	for (int y,x,a = 1 ; a < n ; ++ a)
	x = re() + 1,y = re() + 1,add(y,x);
	dfs1(1),tot = 0,dfs2(1,1);
	for (int w,j,i,mod,m = re() ; m ; -- m) {
		mod = rd(),i = re() + 1;
		if (mod) j = re() + 1,w = re(),update(1,n,1,i,j,w);
		else printf("%lld\n",out(id[i],id[i] + siz[i] - 1));
	}
	return 0;
}