记录编号	383215	评测结果	AAAAAAAAAA
题目名称	2278.[HZOI 2015] 树黑白	最终得分	100
用户昵称	L_in	是否通过	通过
代码语言	C++	运行时间	0.657 s
提交时间	2017-03-15 15:56:31	内存使用	27.22 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 200100
using namespace std;
typedef long long ll;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=10*x+ch-'0',ch=getchar();
	return x*f;
}
int n,m;
struct Edge{
	int to,next,w;
}e[maxn<<1];
int head[maxn],tot;
void add(int from,int to,int w){
	e[++tot].w=w;
	e[tot].to=to;
	e[tot].next=head[from];
	head[from]=tot;
}
int deep[maxn],size[maxn],son[maxn],fa[maxn];
int top[maxn],dfn[maxn],pos[maxn],dfn_cnt;
ll sum[maxn],dis[maxn];int val[maxn];
void dfs(int x){
	size[x]=1;son[x]=0;
	for(int i=head[x];i;i=e[i].next){
		int to=e[i].to;
		if(size[to])continue;
		deep[to]=deep[x]+1;
		val[to]=e[i].w;
		dis[to]=dis[x]+e[i].w;
		fa[to]=x;
		dfs(to);
		size[x]+=size[to];
		if(size[son[x]]<size[to])son[x]=to;
	}
}
void dfs2(int x,int t){
	top[x]=t;dfn[x]=++dfn_cnt;
	pos[dfn_cnt]=x;
	if(son[x])dfs2(son[x],t);
	for(int i=head[x];i;i=e[i].next){
		int to=e[i].to;
		if(!top[to])dfs2(to,to);
	}
}
ll a[maxn<<2],lazy[maxn<<2];
#define mid ((l+r)>>1)
#define L rt<<1,l,mid
#define R rt<<1|1,mid+1,r
void push_down(int rt,int l,int r){
	lazy[rt<<1]+=lazy[rt];
	lazy[rt<<1|1]+=lazy[rt];
	a[rt<<1]+=lazy[rt]*(sum[mid]-sum[l-1]);
	a[rt<<1|1]+=lazy[rt]*(sum[r]-sum[mid]);
	lazy[rt]=0LL;
}
void ins(int rt,int l,int r,int s,int t,int w){
	if(s<=l&&t>=r){
		lazy[rt]+=w;
		a[rt]+=(sum[r]-sum[l-1])*w;
		return;
	}
	if(lazy[rt])push_down(rt,l,r);
	if(s<=mid)ins(L,s,t,w);
	if(t>mid)ins(R,s,t,w);
	a[rt]=a[rt<<1]+a[rt<<1|1];
}
ll qsum(int rt,int l,int r,int s,int t){
	if(s<=l&&t>=r)return a[rt];
	if(lazy[rt])push_down(rt,l,r);
	if(t<=mid)return qsum(L,s,t);
	if(s>mid)return qsum(R,s,t);
	return qsum(L,s,t)+qsum(R,s,t);
}
void ins(int x,int y,int w){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		ins(1,1,n,dfn[top[x]],dfn[x],w);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])swap(x,y);
	ins(1,1,n,dfn[x],dfn[y],w);
}
ll qsum(int x,int y){
	ll ans=0;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		ans+=qsum(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])swap(x,y);
	ans+=qsum(1,1,n,dfn[x],dfn[y]);
	return ans;
}
bool b[maxn];
int main(){
	freopen("A_Tree.in","r",stdin);
	freopen("A_Tree.out","w",stdout);
	n=read();m=read();
	int x,y,w;
	for(int i=1;i<n;i++){
		x=read();y=read();w=read();
		add(x,y,w);add(y,x,w);
	}
	dfs(1);
	dfs2(1,1);
	for(int i=1;i<=dfn_cnt;i++)
		sum[i]=sum[i-1]+val[pos[i]];
	char op[5];
	int cnt=0;ll pre=0LL;
	for(int i=1;i<=m;i++){
		scanf("%s",op);x=read();
		if(op[0]=='M'){
			if(!b[x])ins(1,x,1),cnt++,pre+=dis[x],b[x]=true;
			else ins(1,x,-1),cnt--,pre-=dis[x],b[x]=false;
		}else printf("%lld\n",cnt*dis[x]+pre-2LL*qsum(1,x));
		
	}
	fclose(stdin);fclose(stdout);
	return 0;
}