HDU 5039 Hilarity

  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 }