题意：
n个点n条边的连通图，边长度都为1，没有重边自环，两种操作：
1.把与x距离小于等于k的所有点的权值增加d （k<=2）
2.问离x距离小于等于k的所有点的权值和 （k<=2）
思路：
首先这是个环套树，找到环后从环上的每个点开始bfs，处理出每个点向子树走k步的bfs序区间，一层层维护就好了。
分类讨论比较麻烦。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll lazy[4*N],sum[4*N];
int n;
void init()
{
memset(lazy,0,sizeof(lazy));
memset(sum,0,sizeof(sum));
}
void up(int x)
{
sum[x]=sum[x*2]+sum[x*2+1];
}
void down(int x,int l,int r)
{
if (lazy[x])
{
int mid=(l+r)/2;
sum[x*2]+=(mid-l+1)*lazy[x];
sum[x*2+1]+=(r-mid)*lazy[x];
lazy[x*2]+=lazy[x];
lazy[x*2+1]+=lazy[x];
lazy[x]=0;
}
}
void add(int i,int l,int r,int x,int y,int w)
{
if (x<=l&&r<=y)
{
sum[i]+=w*(r-l+1);
lazy[i]+=w;
return;
}
down(i,l,r);
int mid=(l+r)/2;
if (x<=mid) add(i*2,l,mid,x,y,w);
if (y>mid) add(i*2+1,mid+1,r,x,y,w);
up(i);
}
ll get(int i,int l,int r,int x,int y)
{
if (x<=l&&r<=y) return sum[i];
down(i,l,r);
int mid=(l+r)/2;
ll ret=0;
if (x<=mid) ret+=get(i*2,l,mid,x,y);
if (y>mid) ret+=get(i*2+1,mid+1,r,x,y);
return ret;
}
void ad(int l,int r,int w)
{
if (l>r) return;
add(1,1,n,l,r,w);
}
ll gt(int l,int r)
{
if (l>r) return 0;
return get(1,1,n,l,r);
}
bool vis[N],on[N];
int l[N],r[N];
vector<int>link[N];
int dfs1(int u,int fa)
{
vis[u]=1;
for (int i=0;i<link[u].size();i++)
{
int v=link[u][i];
if (v==fa) continue;
l[v]=u;
if (vis[v]) return v;
int tmp=dfs1(v,u);
if (tmp) return tmp;
}
return 0;
}
int tot;
int q[N],bl[N][3],br[N][3],fa[N];
void bfs(int u)
{
vis[u]=1;
q[++tot]=u;
bl[u][0]=tot; bl[u][1]=bl[u][2]=N;
br[u][0]=tot; br[u][1]=br[u][2]=0;
int head=tot;
while(head<=tot)
{
int u=q[head]; head++;
for (int i=0;i<link[u].size();i++)
{
int v=link[u][i];
if (vis[v]||on[v]) continue;
q[++tot]=v;
bl[v][0]=tot; bl[v][1]=bl[v][2]=N;
br[v][0]=tot; br[v][1]=br[v][2]=0;
fa[v]=u;
vis[v]=1;
}
}
}
void look(int n)
{
for (int i=1;i<=n;i++)
{
printf("%d %lld\n",i,get(1,1,n,bl[i][0],br[i][0]));
}
}
char s[10];
int main()
{
int t; scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
int x,y; scanf("%d%d",&x,&y);
link[x].push_back(y);
link[y].push_back(x);
}
for (int i=1;i<=n;i++) vis[i]=0,on[i]=0;
int root=dfs1(1,1);
r[l[root]]=root; on[root]=1;
for (int i=l[root];i!=root;i=l[i]) r[l[i]]=i,on[i]=1;
tot=0;
for (int i=1;i<=n;i++) vis[i]=0;
bfs(root);
for (int i=l[root];i!=root;i=l[i]) bfs(i);
for (int k=1;k<=2;k++)
for (int i=tot;i>=1;i--)
{
int v=q[i];
if (on[v]) continue;
int u=fa[v];
bl[u][k]=min(bl[u][k],bl[v][k-1]);
br[u][k]=max(br[u][k],br[v][k-1]);
}
init();
int m; scanf("%d",&m);
while(m--)
{
//look(n);
scanf("%s",s);
if (s[0]=='M')
{
int u,k,w; scanf("%d%d%d",&u,&k,&w);
if (k==0) ad(bl[u][0],br[u][0],w);
if (k==1)
{
ad(bl[u][0],br[u][0],w);
ad(bl[u][1],br[u][1],w);//
if (on[u])
{
int lv=l[u],rv=r[u];
ad(bl[lv][0],br[lv][0],w);
ad(bl[rv][0],br[rv][0],w);
}
else
{
int v=fa[u];
ad(bl[v][0],br[v][0],w);
}
}
if (k==2)
{
ad(bl[u][0],br[u][0],w);
ad(bl[u][1],br[u][1],w);
ad(bl[u][2],br[u][2],w);
if (on[u])
{
int lv=l[u];
ad(bl[lv][0],br[lv][0],w);
ad(bl[lv][1],br[lv][1],w);
int rv=r[u];
ad(bl[rv][0],br[rv][0],w);
ad(bl[rv][1],br[rv][1],w);
lv=l[lv];
if (lv!=rv)
ad(bl[lv][0],br[lv][0],w);
else lv=r[lv];
rv=r[rv];
if (rv!=lv)
ad(bl[rv][0],br[rv][0],w);
}
else
{
int v=fa[u];
ad(bl[v][0],br[v][0],w);
ad(bl[v][1],br[v][1],w);
ad(bl[u][0],br[u][0],-w);
if (on[v])
{
int lv=l[v],rv=r[v];
ad(bl[lv][0],br[lv][0],w);
ad(bl[rv][0],br[rv][0],w);
}
else
{
v=fa[v];
ad(bl[v][0],br[v][0],w);
}
}
}
}
if (s[0]=='Q')
{
int u,k,w; scanf("%d%d",&u,&k);
ll ret=0;
if (k==0) ret+=gt(bl[u][0],br[u][0]);
if (k==1)
{
ret+=gt(bl[u][0],br[u][0]);
ret+=gt(bl[u][1],br[u][1]);
if (on[u])
{
int lv=l[u],rv=r[u];
ret+=gt(bl[lv][0],br[lv][0]);
ret+=gt(bl[rv][0],br[rv][0]);
}
else
{
int v=fa[u];
ret+=gt(bl[v][0],br[v][0]);
}
}
if (k==2)
{
ret+=gt(bl[u][0],br[u][0]);
ret+=gt(bl[u][1],br[u][1]);
ret+=gt(bl[u][2],br[u][2]);
if (on[u])
{
int lv=l[u];
ret+=gt(bl[lv][0],br[lv][0]);
ret+=gt(bl[lv][1],br[lv][1]);
int rv=r[u];
ret+=gt(bl[rv][0],br[rv][0]);
ret+=gt(bl[rv][1],br[rv][1]);
lv=l[lv];
if (lv!=rv)
ret+=gt(bl[lv][0],br[lv][0]);
else lv=r[lv];
rv=r[rv];
if (rv!=lv)
ret+=gt(bl[rv][0],br[rv][0]);
}
else
{
int v=fa[u];
ret+=gt(bl[v][0],br[v][0]);
ret+=gt(bl[v][1],br[v][1]);
ret-=gt(bl[u][0],br[u][0]);
if (on[v])
{
int lv=l[v],rv=r[v];
ret+=gt(bl[lv][0],br[lv][0]);
ret+=gt(bl[rv][0],br[rv][0]);
}
else
{
v=fa[v];
ret+=gt(bl[v][0],br[v][0]);
}
}
}
printf("%lld\n",ret);
}
}
for (int i=1;i<=n;i++) link[i].clear();
}
}
/*
1
8
1 2
2 3
3 4
1 4
2 5
3 6
5 7
5 8
12
MODIFY 8 1 5
MODIFY 8 2 2
QUERY 5 0
QUERY 5 1
QUERY 5 2
MODIFY 7 2 2
QUERY 7 2
MODIFY 3 1 5
MODIFY 2 2 2
QUERY 6 1
MODIFY 4 1 -2
QUERY 2 2
*/
