Beijing2014-Online-H.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;
const int N = 30005;

int n , m , pre[N] , mcnt;
struct edge {
    int x , w , next;
}e[N << 1];
map<string , int> hash;
int ncnt , L[N] , R[N];
int q[N] , d[N] , ca;

inline int id(int l , int r) {return l + r | l != r;}
#define MID int mid = l + r >> 1
#define Left l , mid
#define Right mid + 1 , r
struct stree {
    int cnt;
    bool rev;
}t[N << 1];

void Build(int l , int r) {
    int p = id(l , r);
    t[p].rev = 0;
    if (l == r) {
        t[p].cnt = d[l];
        return;
    } MID;
    Build(Left) , Build(Right);
    t[p].cnt = t[id(Left)].cnt + t[id(Right)].cnt;
}

void update(int l , int r , int top , int bot) {
    int p = id(l , r);
    if (top <= l && r <= bot) {
        t[p].cnt = (r - l + 1) - t[p].cnt;
        t[p].rev ^= 1;
        return;
    } MID; int L = id(Left) , R = id(Right);
    if (t[p].rev) {
        t[L].rev ^= 1 , t[R].rev ^= 1;
        t[L].cnt = (mid - l + 1) - t[L].cnt;
        t[R].cnt = (r - mid) - t[R].cnt;
        t[p].rev ^= 1;
    }
    if (top <= mid) update(Left , top , bot);
    if (bot > mid) update(Right , top , bot);
    t[p].cnt = t[L].cnt + t[R].cnt;
}

void dfs(int x , int fa , int w) {
    L[x] = ++ ncnt;
    if (~fa) {
        q[fa >> 1] = x;
    }
    d[ncnt] = w;
    for (int i = pre[x] ; ~i ; i = e[i].next) {
        if (i != fa) {
            dfs(e[i].x , i ^ 1 , w ^ e[i].w);
        }
    }
    R[x] = ncnt;
}

void work() {
    printf("Case #%d:\n" , ++ ca);
    int i , x , y , z;
    char str[15];
    scanf("%d",&n);
    hash.clear();
    for (i = 1 ; i <= n ; ++ i) {
        scanf("%s" , str);
        hash[str] = i;
    }
    memset(pre , -1 , sizeof(pre)) , mcnt = 0;
    for (i = 1 ; i < n ; ++ i) {
        scanf("%s" , str);
        x = hash[str];
        scanf("%s" , str);
        y = hash[str];
        scanf("%d" , &z);
        e[mcnt] = (edge) {y , z , pre[x]} , pre[x] = mcnt ++;
        e[mcnt] = (edge) {x , z , pre[y]} , pre[y] = mcnt ++;
    }
    ncnt = 0;
    dfs(1 , -1 , 0);
    Build(1 , n);
    scanf("%d",&m);
    while (m --) {
        scanf("%s" , str);
        if (*str == 'Q') {
            x = t[id(1 , n)].cnt;
            printf("%I64d\n" , 2LL * x * (n - x));
        } else {
            scanf("%d" , &i);
            i = q[i - 1];
            update(1 , n , L[i] , R[i]);
        }
    }
}


int main() {
    int _; scanf("%d",&_); while (_ --)
        work();
    return 0;
}