记录编号	364070	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 树黑白	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.725 s
提交时间	2017-01-15 10:36:05	内存使用	111.87 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=5e5+10;
struct edge{
	int f,t,l;
	edge(int F=0,int T=0,int L=0){
		f=F;t=T;l=L;
	}
}w[N];
int n,q,head[N],tail[N],next[N];
void add(int f,int t,int l){
	static int cnt=0;
	w[++cnt]=edge(f,t,l);
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	w[++cnt]=edge(t,f,l);
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
int Size,root,size[N],s[N],big[N],fa[N],dep[N];
ll h[N][20];int num[N];
ll up[N],sum[N],dis[N];
bool vis[N],color[N];
void getroot(int x,int fa){
	s[x]=1;big[x]=0;
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (vis[v]||v==fa) continue;
		getroot(v,x);
		s[x]+=s[v];
		big[x]=max(big[x],s[v]);
	}
	if (s[x]>=Size/2&&big[x]<=Size/2) root=x;
}
void geth(int x,int fa){
	h[x][num[x]++]=dis[x];
	s[x]=1;
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (vis[v]||v==fa) continue;
		dis[v]=dis[x]+w[i].l;
		geth(v,x);
		s[x]+=s[v];
	}
}
void build(int x){
	dis[x]=0;geth(x,0);vis[x]=1;
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (vis[v]) continue;
		Size=s[v];
		getroot(v,0);
		fa[root]=x;
		dep[root]=dep[x]+1;
		build(root);
	}
}
void add(int p,int d){
	for (int x=p;x;x=fa[x]){
		sum[x]+=h[p][dep[x]]*d;
		size[x]+=d;
		if (fa[x]) up[x]+=h[p][dep[x]-1]*d;
	}
}
ll query(int x,int p){
	if (!fa[x]) return sum[x];
	return sum[x]+(size[fa[x]]-size[x])*h[p][dep[x]-1]-up[x]+query(fa[x],p);
}
int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
char ch[5];int u;
int main()
{
	freopen("A_Tree.in","r",stdin);
	freopen("A_Tree.out","w",stdout);
	scanf("%d%d",&n,&q);
	for (int i=1,f,t,l;i<n;i++){
		f=read();t=read();l=read();
		add(f,t,l);
	}
	Size=n;getroot(1,0);build(root);
	while (q--){
		scanf("%s",ch);u=read();
		if (ch[0]=='M'){
			if (color[u]) add(u,-1);else add(u,1);
			color[u]^=1;
		}
		else printf("%lld\n",query(u,u));
	}
	return 0;
}