记录编号	395270	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 树黑白	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.701 s
提交时间	2017-04-15 12:33:53	内存使用	65.71 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
const int maxn=200500;
struct Edge{
	int next,to,dis;
}e[maxn<<1];
int len,head[maxn];
void Insert(int x,int y,int z){
	len++;e[len].to=y;e[len].next=head[x];e[len].dis=z;head[x]=len;
}
int n,m; 
int Max[maxn],size[maxn],RT,SUM;
bool vis[maxn];
void getroot(int x,int fa){
	Max[x]=0;size[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(!vis[j] && j!=fa){
			getroot(j,x);
			size[x]+=size[j];
			Max[x]=max(Max[x],size[j]);
		}
	}
	Max[x]=max(Max[x],SUM-size[x]);
	if(Max[x]<Max[RT]) RT=x;
}
int root[maxn],deep[maxn];
int dis[maxn][18],sub[maxn][18];
void Dfs(int x,int fa,int dep,int Sub,int nowdis){
	dis[x][dep]=nowdis;
	sub[x][dep]=Sub;
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(j!=fa && !vis[j])
			Dfs(j,x,dep,Sub,nowdis+e[i].dis);
	}
}
void Build(int x){
	vis[x]=true;
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(!vis[j])
			Dfs(j,0,deep[x],j,e[i].dis);
	}
	getroot(RT,0);
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(!vis[j]){
			SUM=size[j];RT=0;
			getroot(j,0);
			root[RT]=x;
			deep[RT]=deep[x]+1;
			Build(RT);
		}
	}
}
int num[maxn],sum[maxn];
int num_sub[maxn][18],sum_sub[maxn][18];
bool flag[maxn];//0为白色，1为黑色 
inline void Change(int x){
	flag[x]^=1;
	int tp=flag[x] ? 1 : -1;
	num[x]+=tp;
	for(int y=root[x],r=deep[x]-1;y;y=root[y],--r){
		num[y]+=tp;
		num_sub[sub[x][r]][r]+=tp;
		sum[y]+=tp*dis[x][r];
		sum_sub[sub[x][r]][r]+=tp*(dis[x][r]-dis[sub[x][r]][r]);
	}
}
inline int Query(int x){
	int ans=0;
	ans+=sum[x];
	for(int y=root[x],r=deep[x]-1;y;y=root[y],--r){
		ans+=sum[y]-sum_sub[sub[x][r]][r]-dis[sub[x][r]][r]*num_sub[sub[x][r]][r];
		ans+=dis[x][r]*(num[y]-num_sub[sub[x][r]][r]);
	}
	return ans;
}
void Init();
int main(){
	freopen("A_Tree.in","r",stdin);
	freopen("A_Tree.out","w",stdout);
    Init();
    getchar();getchar();
    return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		Insert(x,y,z);Insert(y,x,z);
	}
	RT=0;Max[RT]=Inf;
	SUM=n;getroot(1,0);
	Build(RT);
	while(m--){
		char type;int x;
		scanf(" %c%d",&type,&x);
		if(type=='M') Change(x);
		else printf("%d\n",Query(x));
	}
}