HDU 5274(LCA + 線段樹）

 

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;
}