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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 200010
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;
}
bool b[maxn],vis[maxn];
int rt,cnt,size[maxn],son[maxn];
int dis[20][maxn],sub[20][maxn];//第Deep层x到其rt的dis | 并不知道为什么不是到rt 
int sums[20][maxn],nums[20][maxn];
int fa[maxn],deep[maxn],sum[maxn],num[maxn];//子树中的dis
void g(int x,int fa){
	size[x]=1;son[x]=0;
	for(int i=head[x];i;i=e[i].next){
		int to=e[i].to;
		if(to==fa||vis[to])continue;
		g(to,x);size[x]+=size[to];
		son[x]=max(son[x],size[to]);
	}
	son[x]=max(son[x],cnt-size[x]);
	if(!rt||son[x]<son[rt])rt=x;
}
void reverse(int x){
	b[x]=!b[x];
	int mk=b[x]?1:-1;
	for(int y=x,r=deep[x];y;y=fa[y],r--){
		num[y]+=mk;sum[y]+=mk*dis[r][x];//以i为根的子树黑点个数 | sigma dis
		nums[r][sub[r][x]]+=mk;//r层,rt的某个son的黑点个数
		sums[r][sub[r][x]]+=mk*dis[r][x];//同上
	}
}
int query(int x){
	int ans=sum[x];
	for(int y=fa[x],r=deep[x]-1;y;y=fa[y],r--){
		ans+=sum[y]-sums[r][sub[r][x]];
		ans+=dis[r][x]*(num[y]-nums[r][sub[r][x]]);
	}return ans;
}
void get_deep(int x,int fa,int Sub,int Deep){
	sub[Deep][x]=Sub;//看起来是deep层,x belong rt的哪个son
	for(int i=head[x];i;i=e[i].next){
		int to=e[i].to;
		if(vis[to]||to==fa)continue;
		dis[Deep][to]=dis[Deep][x]+e[i].w;
		get_deep(to,x,Sub,Deep);
	}
}
void build(int x,int Deep){
	for(int i=head[x];i;i=e[i].next){
		int to=e[i].to;
		if(vis[to])continue;
		dis[Deep][to]=e[i].w;//Deep层,to到其rt的dis
		get_deep(to,x,to,Deep);
	}
}
void Build(int x){
	vis[x]=true;
	build(x,deep[x]);//deep[x]层以x为rt
	for(int i=head[x];i;i=e[i].next){
		int to=e[i].to;
		if(vis[to])continue;
		cnt=size[to];rt=0;g(to,x);
		fa[rt]=x;//fa:上一层的rt
		deep[rt]=deep[x]+1;
		Build(rt);
	}
}
int main(){
	freopen("A_Tree.in","r",stdin);
	freopen("A_Tree.out","w",stdout);
	n=read();m=read();
	int u,v,w;
	for(int i=1;i<n;i++){
		u=read();v=read();w=read();
		add(u,v,w);add(v,u,w);
	}
	cnt=n;g(1,0);
	deep[rt]=1;Build(rt);
	char op[5];
	for(int i=1;i<=m;i++){
		scanf("%s",op);u=read();
		if(op[0]=='Q')printf("%d\n",query(u));
		else reverse(u);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}