1
5
a
b
c
d
e
a b 1
b c 0
c d 1
d e 1
7
Q
M 1
Q
M 3
Q
M 4
Q

Case #1:
12
8
8
0

思路：把树形转换成线性的，又涨知识啦，参考官方提供的题解：因为只在乎奇偶性，可以看做求有多少条路径的xor值为1。 随便找个根dfs出根到每个节点路径的xor值d[x]，那么很明显路径的xor值就是两个端点的d[]的xor值。 这样这个问题就比较喜闻乐见了，而修改仅仅是翻转在dfs序上的一个区间，线段树就可以做了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#define lson(x) (x<<1)
#define rson(x) ((x<<1)|1)
typedef long long ll;
using namespace std;
const int maxn = 30005;

map<string, int> mp;
struct Edge {
	int u, v, c;
	Edge() {}
	Edge(int u, int v, int c) {
		this->u = u;
		this->v = v;
		this->c = c;
	} 
};
vector<Edge> edges;
vector<int> g[maxn];
int n, m, q, cnt;
int le[maxn], ri[maxn];
string sa, sb;
int cover[maxn<<2], val[maxn<<2], dep[maxn], ans[maxn<<2];

int id(string s) {
	if (mp.count(s) == 0)
		mp[s] = ++cnt;
	return mp[s];
}

void add(int u, int v, int c) {
	edges.push_back(Edge(u, v, c));
	edges.push_back(Edge(v, u, c));
	m = edges.size();
	g[u].push_back(m-2);
	g[v].push_back(m-1);
}

void dfs(int u, int fa, int va) {
	dep[u] = dep[fa] + 1;
	le[u] = ++cnt;
	val[cnt] = va;
	for (int i = 0; i < g[u].size(); i++) {
		Edge e = edges[g[u][i]];
		int v = e.v;
		int c = e.c;
		if (v == fa) continue;
		dfs(v, u, c^va);
	}
	ri[u] = cnt;
}

void pushup(int pos) {
	ans[pos] = ans[lson(pos)] + ans[rson(pos)];
}

void pushdown(int l, int r, int pos) {
	int m = l + r >> 1;
	if (cover[pos]) {
		cover[lson(pos)] ^= 1;
		cover[rson(pos)] ^= 1;
		ans[lson(pos)] = m - l + 1 - ans[lson(pos)];
		ans[rson(pos)] = r - m - ans[rson(pos)];
		cover[pos] = 0;
	}
}

void build(int l, int r, int pos) {
	if (l == r) {
		cover[pos] = 0;
		ans[pos] = val[l];
		return;
	}
	cover[pos] = 0;
	int m = l + r >> 1;
	build(l, m, lson(pos));
	build(m+1, r, rson(pos));
	pushup(pos);
}

void update(int l, int r, int pos, int L, int R) {
	if (L <= l && R >= r) {
		cover[pos] ^= 1;
		ans[pos] = r - l + 1 - ans[pos];
		return;
	}

	int m = l + r >> 1;
	pushdown(l, r, pos);
	if (L <= m)
		update(l, m, lson(pos), L, R);
	if (R > m)
		update(m+1, r, rson(pos), L, R);
	pushup(pos);
}

int main() {
	int t, cas = 1;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		mp.clear();
		memset(dep, 0, sizeof(dep));
		cnt = 0;
		edges.clear();
		for (int i = 1; i <= n; i++) {
			g[i].clear();
			cin >> sa;
			id(sa);
		}

		for (int i = 0; i < n-1; i++) {
			int u, v, c;
			cin >> sa >> sb;
			scanf("%d", &c);
			u = id(sa);
			v = id(sb);
			add(u, v, c);
		}

		scanf("%d", &q);
		printf("Case #%d:\n", cas++);
		cnt = 0;
		dfs(1, 0, 0);

		build(1, n, 1);
		ll res = 0;
		while (q--) {
			cin >> sa;
			if (sa[0] == 'Q') {
				res = (ll) (n - ans[1]) * ans[1] * 2;
				printf("%lld\n", res);
			}
			else {
				int x;
				scanf("%d", &x);
				x--;
				x <<= 1;
				int u = edges[x].u;
				int v = edges[x].v;
				if (dep[u] < dep[v])
					swap(u, v);
				update(1, n, 1, le[u], ri[u]);
			}
		}
	}
	return 0;
}

HDU Hilarity (dfs序+线段树)