?
Dylans loves tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 747 Accepted Submission(s): 144
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
Hint
If you want to hack someone,N and Q in your testdata must smaller than 10000，and you shouldn't print any space in each end of the line.
Source BestCoder Round #45
Recommend hujie | We have carefully selected several similar problems for you: 5275 5272 5271 5270 5268
?
?
先考虑无修改的情况，令Xor[i]表示i到根节点路径上的异或和，则任意节点的(u,v)的异或和可以转化为Xor[u]^Xor[v]^a[LCA(u,v)].考虑修改的情况，修改节点u，只会以u为根的子树的Xor值产生影响，因为一颗子树的dfs序是连续的我们很自然的想到用线段树去维护他，pSeg[u]表示u在dfs序中的位置，siz[u]表示以u为根的子树大小，则这课颗子树对应的区间就是[pSeg[u],pSeg[u]+siz[u]-1],修改的时候只需要将这段区间先异或上原来的值a[u],在异或上要变成的值y,然后修改a[u] = y;两次异或可以一步到位。直接异或上a[u]^y就行。
?
#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
using namespace std; typedef long long ll; const ll mod = 1e9 + 7; const int maxn = 1e5 + 10; #define to first #define next second #define foreach(it,v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it) int pos[maxn],d[20][maxn<<1],wid[maxn<<1],head[maxn]; int a[maxn],depth[maxn],sid,pSeg[maxn],siz[maxn],Xor[maxn]; typedef pair
Edge; Edge edges[maxn<<1]; int tot = 0,e = 0; void AddEdge(int u,int v) { edges[++e] = make_pair(v,head[u]);head[u] = e; edges[++e] = make_pair(u,head[v]);head[v] = e; } void pre(int u,int fa,int dep = 0,int Xo = 0) { Xo ^= a[u]; Xor[++sid] = Xo; pSeg[u] = sid; siz[u] = 1; d[0][++tot] = u; if(!pos[u]) { pos[u] = tot; depth[u] = dep; } for(int i = head[u]; i ; i = edges[i].next) { int v = edges[i].to; if(v == fa) continue; pre(v,u,dep+1,Xo); siz[u] += siz[v]; d[0][++tot] = u; } } void RMQ_init(int n) { for(int i = 1,w = 1; i <= n; i++) { if((1<
v) swap(u,v); int k = wid[v-u+1]; return depth[d[k][u]] < depth[d[k][v-(1<
=R) { seg[o] ^= x; return ; } push_down(o); int mid = (L+R)>>1; if(ql<=mid) Modify(o<<1,L,mid); if(qr>mid) Modify(o<<1|1,mid+1,R); } int Query(int o,int L,int R) { if(L == R) { return Xor[L] ^ seg[o]; } int mid = (L+R) >>1; push_down(o); if(x<=mid)return Query(o<<1,L,mid); return Query(o<<1|1,mid+1,R); } int main(int argc, char const *argv[]) { int T;scanf("%d",&T); while(T--) { int N,Q;scanf("%d%d",&N,&Q); e = sid = tot = 0; memset(head,0,sizeof(head[0])*(N+1)); for(int i = 1; i < N; i++) { int u,v;scanf("%d%d",&u,&v); AddEdge(u,v); } for(int i = 1; i <= N; i++) { scanf("%d",a+i); ++a[i]; } pre(1,-1); RMQ_init(tot); memset(seg,0,sizeof(seg[0])*(2*N+10)); while(Q--) { scanf("%d%d%d",&x,&ql,&qr); if(x==0) { qr++; int L = pSeg[ql], R = pSeg[ql] + siz[ql] - 1; x = a[ql] ^ qr; a[ql] = qr; ql = L,qr = R; Modify(1,1,N); }else { x = pSeg[ql]; int ans = Query(1,1,N); x = pSeg[qr]; ans ^= Query(1,1,N); ans ^= a[LCA(ql,qr)]; if(ans==0)puts("-1"); else printf("%d\n", ans-1); } } } return 0; }
?
?
?