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;
}
原文：http://blog.csdn.net/u011345136/article/details/40656593