#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 100001

int n;

int front[N],nxt[N<<],to[N<<],tot;

int siz[N],dep[N],fa[N];

int bl[N],son[N];

int id[N],dy[N],cnt;

bool big[N];

int sum0[N<<],sum1[N<<];

bool rev1[N<<],rev2[N<<];

int ans;

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void add(int u,int v)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;

}

void dfs1(int x)

{

    siz[x]=;

    for(int i=front[x];i;i=nxt[i])

        if(to[i]!=fa[x])

        {

            fa[to[i]]=x;

            dep[to[i]]=dep[x]+;

            dfs1(to[i]);

            siz[x]+=siz[to[i]];

        }

}

void dfs2(int x,int top)

{

    bl[x]=top;

    id[x]=++cnt;

    dy[cnt]=x;

    int y=;

    for(int i=front[x];i;i=nxt[i])

        if(to[i]!=fa[x] && siz[to[i]]>siz[y]) y=to[i];

    if(y)

    {

        son[x]=y;

        big[y]=true;

        dfs2(y,top);

    }

    else return;

    for(int i=front[x];i;i=nxt[i])

        if(to[i]!=fa[x] && to[i]!=y) dfs2(to[i],to[i]);

}

void down1(int k)

{

    rev1[k<<]^=;

    swap(sum0[k<<],sum1[k<<]);

    rev1[k<<|]^=;

    swap(sum0[k<<|],sum1[k<<|]);

    rev1[k]^=;

}

void down2(int k)

{

    rev2[k<<]^=;

    rev2[k<<|]^=;

    rev2[k]^=;

}

void Reverse(int k,int l,int r,int opl,int opr,int ty)

{

    if(l>=opl && r<=opr)

    {

        if(ty==)

        {

            swap(sum1[k],sum0[k]);

            rev1[k]^=;

        }

        else rev2[k]^=;

        return;

    }

    int mid=l+r>>;

    if(rev1[k]) down1(k);

    if(rev2[k]) down2(k);

    if(opl<=mid) Reverse(k<<,l,mid,opl,opr,ty);

    if(opr>mid) Reverse(k<<|,mid+,r,opl,opr,ty);

    if(ty==)

    {

        sum1[k]=sum1[k<<]+sum1[k<<|];

        sum0[k]=sum0[k<<]+sum0[k<<|];

    }

}

int get_lca(int u,int v)

{

    while(bl[u]!=bl[v])

    {

        if(dep[bl[u]]<dep[bl[v]]) swap(u,v);

        u=fa[bl[u]];

    }

    return dep[u]<dep[v] ? u : v;

}

bool point_query(int k,int l,int r,int x,int ty)

{

    if(l==r) return ty== ? rev1[k] : rev2[k];

    if(rev1[k]) down1(k);

    if(rev2[k]) down2(k);

    int mid=l+r>>;

    if(x<=mid) return point_query(k<<,l,mid,x,ty);

    return point_query(k<<|,mid+,r,x,ty);

}

void query(int k,int l,int r,int opl,int opr)

{

    if(l>=opl && r<=opr)

    {

        ans+=sum1[k];

        return;

    }

    if(rev1[k]) down1(k);

    if(rev2[k]) down2(k);

    int mid=l+r>>;

    if(opl<=mid) query(k<<,l,mid,opl,opr);

    if(opr>mid) query(k<<|,mid+,r,opl,opr);

}

void solve(int ty,int u,int v)

{

    if(ty==)

    {

        while(bl[u]!=bl[v])

        {

            if(dep[bl[u]]<dep[bl[v]]) swap(u,v);

            Reverse(,,n,id[bl[u]],id[u],);

            u=fa[bl[u]];

        }

        if(dep[u]>dep[v]) swap(u,v);

        if(u!=v) Reverse(,,n,id[u]+,id[v],);

    }

    else if(ty==)

    {

        int lca=get_lca(u,v);

        if(lca!=u && lca!=v)

        {

            if(big[lca]) Reverse(,,n,id[lca],id[lca],);

        }

        else

        {

            if(dep[u]>dep[v]) swap(u,v);

            if(big[u]) Reverse(,,n,id[u],id[u],);

        }

        while(bl[u]!=bl[v])

        {

            if(dep[bl[u]]<dep[bl[v]]) swap(u,v);

            if(son[u]) Reverse(,,n,id[son[u]],id[son[u]],);

            Reverse(,,n,id[bl[u]],id[u],);

            u=fa[bl[u]];

        }

        if(dep[u]>dep[v]) swap(u,v);

        if(son[v]) Reverse(,,n,id[son[v]],id[son[v]],);

        Reverse(,,n,id[u],id[v],);

    }

    else

    {

        ans=;

        while(bl[u]!=bl[v])

        {

            if(dep[bl[u]]<dep[bl[v]]) swap(u,v);

            query(,,n,id[bl[u]],id[u]);

            ans+=point_query(,,n,id[bl[u]],)^point_query(,,n,id[fa[bl[u]]],)^point_query(,,n,id[bl[u]],);

            u=fa[bl[u]];

        }

        if(dep[u]>dep[v]) swap(u,v);

        if(u!=v) query(,,n,id[u]+,id[v]);

        printf("%d\n",ans);

    }

}    

void build(int k,int l,int r)

{

    sum0[k]=sum1[k]=;

    rev1[k]=rev2[k]=false;

    if(l==r)

    {

        sum0[k]=big[dy[l]];

        return;

    }

    int mid=l+r>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    sum0[k]=sum0[k<<]+sum0[k<<|];

}

void clear()

{

    tot=cnt=;

    memset(front,,sizeof(front));

    memset(son,,sizeof(son));

    memset(big,false,sizeof(big));

}

int main()

{

    freopen("data.in","r",stdin);

    freopen("my.out","w",stdout);

    int T;

    read(T);

    int u,v;

    int ty,m,lca;

    while(T--)

    {

        clear();

        read(n);

        for(int i=;i<n;++i)

        {

            read(u); read(v);

            add(u,v);

        }

        dfs1();

        dfs2(,);

        build(,,n);

        read(m);

        while(m--)

        {

            read(ty); read(u); read(v);

            solve(ty,u,v);

        }

    }

    return ;

}

Problem Description

There is an old country and the king fell in love with
a devil. The devil always asks the king to do some crazy things. Although the
king used to be wise and beloved by his people. Now he is just like a boy in
love and can’t refuse any request from the devil. Also, this devil is looking
like a very cute Loli.

The devil likes to make thing in chaos. This
kingdom’s road system is like simply a tree(connected graph without cycle). A
road has a color of black or white. The devil often wants to make some change of
this system.

In details, we call a path on the tree from a to b consists
of vertices lie on the shortest simple path between a and b. And we say an edge
is on the path if both its two endpoints is in the path, and an edge is adjacent
to the path if exactly one endpoint of it is in the path.

Sometimes the
devil will ask you to reverse every edge’s color on a path or adjacent to a
path.

The king’s daughter, WJMZBMR, is also a cute loli, she is surprised
by her father’s lolicon-like behavior. As she is concerned about the
road-system’s status, sometimes she will ask you to tell there is how many black
edge on a path.

Initially, every edges is white.

 

Input

The first line contains an integer T, denoting the
number of the test cases.
For each test case, the first line contains an
integer n, which is the size of the tree. The vertices be indexed from 1.
On
the next n-1 lines, each line contains two integers a,b, denoting there is an
edge between a and b.
The next line contains an integer Q, denoting the
number of the operations.
On the next Q lines, each line contains three
integers t,a,b. t=1 means we reverse every edge’s color on path a to b. t=2
means we reverse every edge’s color adjacent to path a to b. t=3 means we query
about the number of black edge on path a to
b.

T<=5.
n,Q<=10^5.
Please use scanf,printf instead of
cin,cout,because of huge input.

 

Output

For each t=3 operation, output the answer in one
line.

 

Sample Input

 

Sample Output

 

Author

WJMZBMR