题意：

一棵树上有些边是1有些是0  问  有几条简单路径路过奇数个1  树上的边的1和0可以修改

思路：

不会做…  看题解才找到思路… TAT

首先要明确一点  对于u->v这条路径  它的奇偶是可以通过root->u和root->v计算的  因为如果从root出发的两路径不相交  那么两路径上的1相加即可判断u->v  如果相交  假设相交部分有x个1  那么对于u->v的1的个数即为两路径相加  再减去2x  很明显减2x不影响奇偶性  因此本题可以得出结论  如果从root出发有y个奇数路径  则答案为 y*((n-1)-y+1) = y*(n-y)  式子中用(n-1)是因为不算root  后面+1是因为奇数路径可以直接当答案不与偶数路径拼接

知道了如何求答案  再来想如何维护边修改  我们发现  修改一条边fu->fv  只影响fv子树中的奇偶性  那么可以用dfs序表示出树的线性结构  再通过线段树区间更新来达到目的

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cassert>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long LL;
#define N 30010
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
#define MI(x,y) ((x+y)>>1)

int T, t, n, m, tot, idx;
int head[N], l[N], r[N], val[N];
struct edge {
	int u, v, flag, next;
} ed[N * 2];
map<string, int> hash;
struct tree {
	int l, r, odd, lazy;
} d[N * 4];

void add(int u, int v, int f) {
	ed[tot].u = u;
	ed[tot].v = v;
	ed[tot].flag = f;
	ed[tot].next = head[u];
	head[u] = tot++;
}

void dfs(int u, int f, int fa) {
	idx++;
	val[idx] = f;
	l[u] = idx;
	for (int i = head[u]; ~i; i = ed[i].next) {
		if (ed[i].v != fa)
			dfs(ed[i].v, f ^ ed[i].flag, u);
	}
	r[u] = idx;
}

void down(int i) {
	if (d[i].lazy) {
		d[L(i)].lazy ^= 1;
		d[R(i)].lazy ^= 1;
		d[L(i)].odd = d[L(i)].r - d[L(i)].l + 1 - d[L(i)].odd;
		d[R(i)].odd = d[R(i)].r - d[R(i)].l + 1 - d[R(i)].odd;
		d[i].lazy = 0;
	}
}

void up(int i) {
	d[i].odd = d[L(i)].odd + d[R(i)].odd;
}

void init(int l, int r, int i) {
	d[i].l = l;
	d[i].r = r;
	d[i].lazy = 0;
	d[i].odd = val[l];
	if (l == r)
		return;
	int mid = MI(l,r);
	init(l, mid, L(i));
	init(mid + 1, r, R(i));
	up(i);
}

void update(int l, int r, int i) {
	if (d[i].l == l && d[i].r == r) {
		d[i].odd = d[i].r - d[i].l + 1 - d[i].odd;
		d[i].lazy ^= 1;
		return;
	}
	down(i);
	int mid = MI(d[i].l,d[i].r);
	if (r <= mid)
		update(l, r, L(i));
	else if (l > mid)
		update(l, r, R(i));
	else {
		update(l, mid, L(i));
		update(mid + 1, r, R(i));
	}
	up(i);
}

int main() {
	int i, u, v, f;
	char str[50], uu[50], vv[50];
	scanf("%d", &T);
	for (t = 1; t <= T; t++) {
		printf("Case #%d:\n", t);
		hash.clear();
		scanf("%d", &n);
		for (i = 1; i <= n; i++) {
			scanf("%s", str);
			hash[string(str)] = i;
			head[i] = -1;
		}
		tot = 0;
		for (i = 1; i < n; i++) {
			scanf("%s%s%d", uu, vv, &f);
			u = hash[string(uu)];
			v = hash[string(vv)];
			add(u, v, f);
			add(v, u, f);
		}
		idx = 0;
		dfs(1, 0, 0);
		init(1, n, 1);
		scanf("%d", &m);
		while (m--) {
			scanf("%s", str);
			if (str[0] == 'Q')
				printf("%d\n", d[1].odd * (n - d[1].odd) * 2);
			else {
				scanf("%d", &f);
				f = (f - 1) * 2;
				u = ed[f].u;
				v = ed[f].v;
				if (l[u] > l[v])
					update(l[u], r[u], 1);
				else
					update(l[v], r[v], 1);
			}
		}
	}
	return 0;
}

HDU 5039 Hilarity