1 #include <cstdio>  2 #include <iostream>  3 #include <vector>  4 #include <map>  5 #include <cstring>  6 #include <cmath>  7 #include <algorithm>  8 #include <set>  9 #define pb push_back 10 #define mp make_pair 11  12 #define lson   l, m, rt<<1 13 #define rson   m+1, r, rt<<1|1 14 #define sz(x) ((int)((x).size())) 15 #define pb push_back 16 #define in freopen("data.txt", "r", stdin); 17 #define bug(x) printf("Line : %u >>>>>>\n", (x)); 18 #define inf 0x0f0f0f0f 19 using namespace std; 20 typedef pair<int, int> PII; 21 typedef map<string, int> MPS; 22 typedef long long LL; 23  24 const int maxn = 30000 + 100; 25 MPS mps; 26  27 struct Edge { 28     int u, v, c; 29     Edge() {} 30     Edge(int u, int v, int c):u(u), v(v), c(c) {} 31 }; 32 vector<Edge> edges; 33 vector<int> g[maxn]; 34  35 int n, m, q, cnt; 36 int le[maxn], ri[maxn]; 37  38 int idx(char *s) { 39     if(mps.count(s) == false) 40         mps[s] = ++cnt; 41     return mps[s]; 42 } 43  44 void add(int u, int v, int c) { 45     edges.pb(Edge(u, v, c)); 46     edges.pb(Edge(v, u, c)); 47     m = edges.size(); 48     g[u].pb(m-2); 49     g[v].pb(m-1); 50 } 51 char sa[20], sb[20]; 52 int cover[maxn<<2], val[maxn], dep[maxn], ans[maxn<<2]; 53 void PushUp(int rt) { 54     ans[rt] = ans[rt<<1]+ans[rt<<1|1]; 55 } 56 //线段树的每个结点要初始化！！！！ 57  58 void PushDown(int l, int r, int rt) { 59     int m = (l+r)>>1; 60     if(cover[rt]) { 61         cover[rt<<1] ^= 1; 62         cover[rt<<1|1] ^= 1; 63         ans[rt<<1] = m-l+1-ans[rt<<1]; 64         ans[rt<<1|1] = r-m-ans[rt<<1|1]; 65         cover[rt] = 0; 66     } 67 } 68 void build(int l, int r, int rt) { 69     if(l == r) { 70         cover[rt] = 0; 71         ans[rt] = val[l]; 72         return; 73     } 74     cover[rt] = 0; 75     int m = (l+r)>>1; 76     build(lson); 77     build(rson); 78     PushUp(rt); 79 } 80 void update(int l, int r, int rt, int L, int R) { 81     if(L <= l && R >= r) { 82         cover[rt] ^= 1; 83         ans[rt] = r-l+1-ans[rt]; 84         return; 85     } 86  87     int m = (l+r)>>1; 88     PushDown(l, r, rt); 89     if(L <= m) 90         update(lson, L, R); 91     if(R > m) 92         update(rson, L, R); 93     PushUp(rt); 94 } 95 void dfs(int u, int fa, int va) { 96     dep[u] = dep[fa] + 1; 97     le[u] = ++cnt; 98     val[cnt] = va; 99     for(int i = 0; i < (int)g[u].size(); i++) {100         Edge e = edges[g[u][i]];101         int v = e.v;102         int c = e.c;103         if(v == fa) continue;104         dfs(v, u, c^va);105     }106     ri[u] = cnt;107 }108 int main() {109 110     int T;111     int kase = 0;112     for(int t = scanf("%d", &T); t <= T; t++) {113         scanf("%d", &n);114         mps.clear();115         cnt = 0;116         edges.clear();117         for(int i = 1; i <= n; i++) {118             g[i].clear();119             scanf("%s", sa);120             idx(sa);121         }122         for(int i = 0; i < n-1; i++) {123             int c, u, v;124             scanf("%s%s%d", sa, sb, &c);125             u = idx(sa);126             v = idx(sb);127             add(u, v, c);128         }129         scanf("%d", &q);130         printf("Case #%d:\n", ++kase);131         cnt = 0;132         dfs(1, 0, 0);133         build(1, n, 1);134         LL res = 0;135         while(q--) {136             scanf("%s", sa);137             if(sa[0] == ‘Q‘) {138                 res = (LL)(n-ans[1])*ans[1]*2;139                 printf("%I64d\n", res);140             } else {141                 int x;142                 scanf("%d", &x);143                 x--;144                 x <<= 1;145                 int u = edges[x].u;146                 int v = edges[x].v;147                 if(dep[u] < dep[v]) swap(u, v);148                 update(1, n, 1, le[u], ri[u]);149             }150         }151     }152     return 0;153 }