记录编号	254694	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 树黑白	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.756 s
提交时间	2016-04-25 16:41:15	内存使用	20.17 MiB

#include<stdio.h>
inline void in(int &x){for(x=getchar();x<48||x>57;x=getchar());x^=48;for(int tmp=getchar();47<tmp&&tmp<58;tmp=getchar())x=(x<<1)+(x<<3)+(tmp^48);}
int n,m,shu,first[200010];
struct edge{int v,w,nx;}o[400010];
inline void add(int u,int v,int w){
	o[++shu].v=v,o[shu].w=w,o[shu].nx=first[u],first[u]=shu;
}
int s[200010],son[200010];
bool vis[200010];
inline void dfs(int x,int last){
	s[x]=1,son[x]=0;
	for(int i=first[x];i;i=o[i].nx)
	    if(o[i].v!=last&&!vis[o[i].v]){
			dfs(o[i].v,x),s[x]+=s[o[i].v];
			if(s[son[x]]<s[o[i].v])son[x]=o[i].v;
	    }
}
inline int G(int x){
	dfs(x,x);
	for(int tmp=s[x]>>1;s[son[x]]>tmp;x=son[x]);
	return x;
}
bool mk[200010];
int f[200010],g[200010],num[200010],fa[200010][20],d[200010][20];
inline void get(int x,int last,int dis,int G_,int dep){
	d[x][dep]=dis,fa[x][dep]=G_;
	for(int i=first[x];i;i=o[i].nx)
	    if(o[i].v!=last&&!vis[o[i].v])
	        get(o[i].v,x,dis+o[i].w,G_,dep);
}
inline void DFS(int x,int dep){
	vis[x]=1,fa[x][dep]=x;
	for(int i=first[x];i;i=o[i].nx)
	    if(!vis[o[i].v]){
			get(o[i].v,x,o[i].w,x,dep);
			DFS(G(o[i].v),dep+1);
	    }
}
inline void off(int x){
	mk[x]=0;int i;
	for(i=19;;--i)if(fa[x][i])break;
	for(;~i;--i){
		--num[fa[x][i]],g[fa[x][i]]-=d[x][i];
		if(i)f[fa[x][i]]-=d[x][i-1];
	}
}
inline void on(int x){
	mk[x]=1;int i;
	for(i=19;;--i)if(fa[x][i])break;
	for(;~i;--i){
		++num[fa[x][i]],g[fa[x][i]]+=d[x][i];
		if(i)f[fa[x][i]]+=d[x][i-1];
	}
}
inline int query(int x){
	int ans;int i;
	for(i=19;;--i)if(fa[x][i])break;
	for(ans=g[fa[x][i--]];~i;--i){
		ans+=g[fa[x][i]]-f[fa[x][i+1]];
		ans+=(num[fa[x][i]]-num[fa[x][i+1]])*d[x][i];
	}
	return ans;
}
bool work(){
	freopen("A_Tree.in","r",stdin);
	freopen("A_Tree.out","w",stdout);
	in(n),in(m);
	for(int i=1,u,v,w;i<n;++i)in(u),in(v),in(w),add(u,v,w),add(v,u,w);
	DFS(G(1),0);char ch[2];
	for(int i=1,x;i<=m;++i){
		scanf("%s%d",ch,&x);
		if(*ch=='M'){
			if(mk[x])off(x);
			else on(x);
		}else printf("%d\n",query(x));
	}
}
bool tt=work();
main(){;}