hdu 5274 Dylans loves tree

Dylans loves tree

http://acm.hdu.edu.cn/showproblem.php?pid=5274

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

Dylans is given a tree with N nodes.

All nodes have a value A[i] .Nodes on tree is numbered by 1∼N .

Then he is given Q questions like that:

①0 x y ：change node x′s value to y 

②1 x y ：For all the value in the path from x to y ,do they all appear even times?

For each ② question,it guarantees that there is at most one value that appears odd times on the path.

1≤N,Q≤100000 , the value A[i]∈N and A[i]≤100000

 

 

Input

In the first line there is a test number T .
(T≤3 and there is at most one testcase that N>1000 )

For each testcase:

In the first line there are two numbers N and Q .

Then in the next N−1 lines there are pairs of (X,Y) that stand for a road from x to y .

Then in the next line there are N numbers A1..AN stand for value.

In the next Q lines there are three numbers(opt,x,y) .

 

Output

For each question ② in each testcase,if the value all appear even times output "-1",otherwise output the value that appears odd times.

 

Sample Input

1

3 2

1 2

2 3

1 1 1

1 1 2

1 1 3

 

Sample Output

-1 1

 

题目大意：给出一颗n个点的树，有q个操作，点有点权。

操作① 0,x,y 修改x的点权为y

操作② 1,x,y 询问点x到点y是否有出现过奇数次的权值，有则输出，无则输出-1。输入保证至多有一个出现过一次的权值

基本框架：树链剖分+线段树

思路：单点修改+询问区间异或和

若k出现过偶数次，则这些k的异或和为0

若只有1个k出现过奇数次，那异或的结果=k

一个小细节：

因为0无论异或多少次都是0，所以将所有数都+1，输出答案-1

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100001
using namespace std;
struct node
{
    int l,r,key;
    void clear() {l=r=key=0;}
}tr[N*2];
struct edge{int next,to;}e[N*2];
int id[N],dep[N],son[N],fa[N],bl[N],sz,e_tot,tr_tot,T,n,q,head[N];
inline void add(int u,int v)
{
    e[++e_tot].to=v;e[e_tot].next=head[u];head[u]=e_tot;
    e[++e_tot].to=u;e[e_tot].next=head[v];head[v]=e_tot;
}
inline void dfs1(int x,int f)
{
    son[x]++;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].to==fa[x]) continue;
        dep[e[i].to]=dep[x]+1;
        fa[e[i].to]=x;
        dfs1(e[i].to,x);
        son[x]+=son[e[i].to];
    }
} 
inline void dfs2(int x,int chain)
{
    sz++;
    bl[x]=chain;
    id[x]=sz;
    int y=0;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].to==fa[x]) continue;
        if(son[e[i].to]>son[y]) y=e[i].to;
    }
    if(!y) return;
    dfs2(y,chain);
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].to==fa[x]||e[i].to==y) continue;
        dfs2(e[i].to,e[i].to);
    }
}
inline void build(int l,int r)
{
    tr_tot++; tr[tr_tot].clear();
    tr[tr_tot].l=l;tr[tr_tot].r=r;
    if(l==r) return;
    int mid=l+r>>1;
    build(l,mid);build(mid+1,r);
}
inline void change(int k,int x,int w)
{
    if(tr[k].l==tr[k].r) {tr[k].key=w;return;}
    int mid=tr[k].l+tr[k].r>>1,l=k+1,r=k+(tr[k+1].r-tr[k+1].l+1<<1);
    if(x<=mid) change(l,x,w);
    else change(r,x,w);
    tr[k].key=tr[l].key^tr[r].key;
}
inline int query(int k,int opl,int opr)
{
    if(tr[k].l>=opl&&tr[k].r<=opr) {return tr[k].key;}
    int mid=tr[k].l+tr[k].r>>1,l=k+1,r=k+(tr[k+1].r-tr[k+1].l+1<<1);
    int tmp=0;
    if(opl<=mid) tmp=query(l,opl,opr);
    if(opr>mid) tmp^=query(r,opl,opr);
    return tmp;
}
inline void solve_query(int u,int v)
{
    int ans=0;
    while(bl[u]!=bl[v])
    {
        if(dep[bl[u]]<dep[bl[v]]) swap(u,v);
        ans^=query(1,id[bl[u]],id[u]);
        u=fa[bl[u]];
    }
    if(id[u]>id[v]) swap(u,v);
    ans^=query(1,id[u],id[v]);
    printf("%d
",ans-1);
}
inline void solve()
{
    int p,x,y;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&x);
        change(1,id[i],x+1);
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&p,&x,&y);
        if(!p) change(1,id[x],y+1);
        else solve_query(x,y);
    }
}
inline void pre()
{
    memset(son,0,sizeof(son));
    memset(head,0,sizeof(head));
    memset(fa,0,sizeof(fa));
    memset(dep,0,sizeof(dep));
    sz=e_tot=tr_tot=0;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        pre();
        scanf("%d%d",&n,&q);
        int u,v;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        dfs1(1,0);
        dfs2(1,1);
        build(1,n);
        solve();
    }
}