题目大意：

输入一颗 n(n≤30000) $n(n\le 30000)$个点的无根的边权树，边权值域 {0,1} $\{0,1\}$。
之后有 m(m≤60000) $m(m\le 60000)$次操作，操作分为两种。
第一种：修改某一条边的权值（从0变1 或 从1变0）；
第二种：查询整棵树有多少条不同的路径满足，路径权值和为奇数。

分析：

首先如果仅仅是一次查询，显然会选择一次 O(n) $O\left(n\right)$ 的 dfs $dfs$ 搜索就可以得到答案了，但是标准答案提供了一种更加优秀的办法。

首先为了简化问题，选择一个节点作为根节点，然后我们可以发现，如果改变某一条边的值的只有经过这条边所有路径的长度的奇偶性完全改变。但是这样也还是并没有有效的利用到树结构的性质。

这里非常巧妙地引入一个量： dp[i] $dp\left[i\right]$ 表示 i $i$ 号节点到根节点的路径长度的奇偶性（长度异或和）。这样树上任意两个点 (u,v) $(u,v)$之间简单路径的长度的奇偶性就和从一个结点到根节点再到另一个结点的路径长度的奇偶性是一样的，因为他们走的公共长度 lca(u,v) $lca(u,v)$ 走了两遍，相互抵消。所以我只需要通过 dfs $dfs$ 序压缩成区间，然后维护区间 dp $dp$ 值就可以了。
（1）每次修改相当于是一个子树的数值全部取反，也就是区间异或 1 $1$。
（2）每次查询区间和即到根节点距离的长度为奇数的点的个数乘偶数的点的个数即为答案。也就是查询总区间和即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 30052
map<string,int>c;
vector<int>a[maxn],w[maxn],w0[maxn];
int pos[maxn],siz[maxn],id[maxn];
int lazy[maxn<<2],tr[maxn<<2],b[maxn];
int n,m,cnt;
bool vis[maxn];
void init()
{
    c.clear();
    memset(lazy,0,sizeof(lazy));
    for(int i=0;i<=n;i++)
    {
        vis[i]=0;
        w0[i].clear();
        w[i].clear();
        a[i].clear();
    }
    cnt=1;
}
void dfs(int x,int val)
{
    int ret=1;
    vis[x]=1;
    pos[x]=cnt;
    b[cnt++]=val;
    for(int i=0;i<a[x].size();i++)
    {
        if(vis[a[x][i]])continue;
        dfs(a[x][i],val^w[x][i]);
        ret+=siz[a[x][i]];
        id[w0[x][i]]=a[x][i];
    }
    siz[x]=ret;
}
void pushup(int now)
{
    tr[now]=tr[now<<1]+tr[now<<1|1];
}
void pushdown(int nl,int nr,int now)
{
    if(lazy[now])
    {
        int mid=(nl+nr)>>1;
        tr[now<<1]=(mid-nl+1)-tr[now<<1];
        lazy[now<<1]^=lazy[now];
        tr[now<<1|1]=(nr-mid)-tr[now<<1|1];
        lazy[now<<1|1]^=lazy[now];
        lazy[now]=0;
    }
}
void build(int nl,int nr,int now)
{
    if(nl==nr)
    {
        tr[now]=b[nl];
        return;
    }
    int mid=(nl+nr)>>1;
    build(nl,mid,now<<1);
    build(mid+1,nr,now<<1|1);
    pushup(now);
}
int query(int l,int r,int nl,int nr,int now)
{
    if(l<=nl&&nr<=r)
    {
        return tr[now];
    }
    int ret=0,mid=(nl+nr)>>1;
    pushdown(nl,nr,now);
    if(l<=mid)ret+=query(l,r,nl,mid,now<<1);
    if(r>mid)ret+=query(l,r,mid+1,nr,now<<1|1);
    return ret;
}
void updata(int l,int r,int add,int nl,int nr,int now)
{
    if(l<=nl&&nr<=r)
    {
        lazy[now]^=1;
        tr[now]=(nr-nl+1)-tr[now];
        return;
    }
    int mid=(nl+nr)>>1;
    pushdown(nl,nr,now);
    if(l<=mid)updata(l,r,add,nl,mid,now<<1);
    if(r>mid)updata(l,r,add,mid+1,nr,now<<1|1);
    pushup(now);
}
int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        printf("Case #%d:\n",cas++);
        scanf("%d",&n);
        char temp1[100],temp2[100];
        int temp;
        string s1,s2;
        init();
        for(int i=1;i<=n;i++)
        {
            scanf("%s",&temp1);
            s1=temp1;
            c[s1]=i;
        }
        for(int i=1;i<n;i++)
        {
            scanf("%s%s%d",temp1,temp2,&temp);
            s1=temp1;s2=temp2;
            int ts=c[s1],te=c[s2];
            a[ts].push_back(te);
            a[te].push_back(ts);
            w[ts].push_back(temp);
            w[te].push_back(temp);
            w0[ts].push_back(i);
            w0[te].push_back(i);
        }
        dfs(1,0);
        /*for(int i=1;i<n;i++) { printf("%d %d\n",i,pos[i]); }*/
        build(1,n,1);
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%s",temp1);
            if(temp1[0]=='Q')
            {
                int ans=0;
                ans=query(1,n,1,n,1);
                ans=(n-ans)*ans*2;
                printf("%d\n",ans);
            }
            else
            {
                int x;
                scanf("%d",&x);
                int t=id[x];
                updata(pos[t],pos[t]+siz[t]-1,1,1,n,1);
            }
        }
    }

}

总结：

突然发现，对于解决树上相关的问题，这一类想法是非常巧妙的，典型的就是树上异或相关的问题。包括前几天做的权值并查集题目，在计算两个点简单路径长度的时候，可以考虑该数值和两个点到根节点的距离的关系。例如距离定义为异或和的时候，这里就显然抵消掉了。