记录编号	365523	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 树黑白	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.687 s
提交时间	2017-01-20 19:25:27	内存使用	72.03 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cctype>
using namespace std;
int read() {
	int x=0; char ch;
	while(ch=getchar(), !isdigit(ch));
	x = ch-'0';
	while(ch=getchar(), isdigit(ch)) x = x*10+ch-'0';
	return x;
}
const int maxn = 200005, maxd = 20;
struct Edge {
	int next, to, dis;
	Edge(int a=0, int b=0, int c=0) :
		next(a), to(b), dis(c) {}
} e[maxn<<1];
int head[maxn], tot;
void Add(int u, int v, int w) {
	e[++tot] = Edge(head[u], v, w); head[u] = tot;
}
int N, Q, F, Size, root, size[maxn], vis[maxn];
int fa[maxn], res[maxn];
int dis[maxn][maxd], sub[maxn][maxd];
int sum[maxn], num[maxn], black[maxn];
int sums[maxn][maxd], nums[maxn][maxd];
 
void invert(int x) {
	black[x] ^= 1;
	int mk = black[x] ? 1 : -1;
	num[x] += mk;
	for(int y=fa[x], r=res[x]-1; y; y=fa[y], --r) {
		num[y] += mk;
		sum[y] += mk*dis[x][r];
		nums[sub[x][r]][r] += mk;
		sums[sub[x][r]][r] += mk*dis[x][r];
	}
}
int query(int x) {
	int ans = sum[x]; //warn
	for(int y=fa[x], r=res[x]-1; y; y=fa[y], --r) {
		ans += sum[y]-sums[sub[x][r]][r];
		ans += dis[x][r]*(num[y]-nums[sub[x][r]][r]);
	}
	return ans;
}
void getdep(int x, int fa, int Sub, int Res) {
	sub[x][Res] = Sub;
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to] || to==fa) continue;
		dis[to][Res] = dis[x][Res]+e[i].dis;
		getdep(to, x, Sub, Res);
	}
}
void build(int x) {
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to]) continue;
		dis[to][res[x]] = e[i].dis;
		getdep(to, x, to, res[x]);
	}
}
int getroot(int x, int fa) {
	int f = 0; size[x] = 1;
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to] || to==fa) continue;
		size[x] += getroot(to, x);
		f = max(f, size[to]);
	}
	f = max(f, Size-size[x]);
	if(f<=F) F = f, root = x;
	return size[x];
}
void Build(int x) {
	vis[x] = 1; build(x);
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to]) continue;
		F = Size = size[to]; getroot(to, -1);
		fa[root] = x;
		res[root] = res[x]+1;
		Build(root); 
	}
}
int main() {
	freopen("A_Tree.in","r",stdin);
	freopen("A_Tree.out","w",stdout);
	N = read(), Q = read();
	for(int i=1,a,b,c; i<N; ++i) {
		a = read(), b = read(), c = read();
		Add(a, b, c); Add(b, a, c);
	}
	F = Size = N; getroot(1, -1);
	res[root] = 1, Build(root);
	char ch[2]; int v;
	while(Q--) {
		scanf("%s", ch); v = read();
		if(ch[0]=='Q') printf("%d\n", query(v));
		else invert(v);
	}
	getchar(), getchar();
	return 0;
}