记录编号	493988	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 树黑白	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	1.373 s
提交时间	2018-04-07 17:42:58	内存使用	11.99 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010;
struct poi{int u,w;};
vector<poi>p[maxn];
int n,m,Sum,root,c[maxn],T[maxn][3],S[maxn][3];
int fa[maxn],sz[maxn],Fa[maxn],siz[maxn],son[maxn],dep[maxn],top[maxn];
bool vis[maxn];
long long ans,dis[maxn];
/*T[i][0]:在动态树中,以i为根的子树中黑点的个数
  T[i][1]:在动态树中,i到Fa[i]之间的黑点个数
  S[i][0]:在动态树中,以i为根的子树中黑点到i的距离和
  S[i][1]:在动态树中,i到Fa[i]之间黑点到Fa[i]的距离和*/
void getroot(int x,int fa){
	sz[x]=0,siz[x]=1;
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i].u;
		if(vis[u]||u==fa)continue;
		getroot(u,x);
		siz[x]+=siz[u];
		sz[x]=max(sz[x],siz[u]);
	}
	sz[x]=max(sz[x],Sum-siz[x]);
	if(sz[x]<sz[root])root=x;
}
void dfs1(int x){
	siz[x]=1;
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i].u,w=p[x][i].w;
		if(u==fa[x])continue;
		fa[u]=x,dep[u]=dep[x]+1,dis[u]=dis[x]+w;
		dfs1(u);
		siz[x]+=siz[u];
		if(siz[u]>siz[son[x]])son[x]=u;
	}
}
void dfs2(int x,int y){
	top[x]=y;
	if(!son[x])return;
	dfs2(son[x],y);
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i].u;
		if(u==son[x]||u==fa[x])continue;
		dfs2(u,u);
	}
}
int lca(int x,int y){
	int f1=top[x],f2=top[y];
	while(f1!=f2){
		if(dep[f1]<dep[f2])swap(x,y),swap(f1,f2);
		x=fa[f1],f1=top[x];
	}
	if(dep[x]>dep[y])swap(x,y);
	return x;
}
int dist(int x,int y){return dis[x]+dis[y]-2*dis[lca(x,y)];}
void solve(int x){
	vis[x]=1;
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i].u;
		if(vis[u])continue;
		Sum=siz[u],root=0,getroot(u,0);
		Fa[root]=x,solve(root);
	}
}
int main(){
	freopen("A_Tree.in","r",stdin);
	freopen("A_Tree.out","w",stdout);
	scanf("%d%d",&n,&m);
	int u,v,w;char op[5];
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		p[u].push_back((poi){v,w});
		p[v].push_back((poi){u,w});
	}
	sz[0]=Sum=n;
	dfs1(1);dfs2(1,1);getroot(1,0);solve(root);
	while(m--){
		scanf("%s%d",op,&u);
		int d,p,h=u;
		if(op[0]=='Q'){
			ans=S[u][0];
			for(;Fa[u];u=Fa[u]){
				p=Fa[u],d=dist(h,p);
				ans+=(long long)(T[p][0]-T[u][1])*d+S[p][0]-S[u][1];
			}
			printf("%lld\n",ans);
		}
		else{
			w=c[u]?-1:1;c[u]^=1,T[u][0]+=w;
			for(;Fa[u];u=Fa[u]){
				p=Fa[u],d=dist(h,p)*w;
				T[p][0]+=w,T[u][1]+=w,S[p][0]+=d,S[u][1]+=d;
			}
		}
	}
	return 0;
}