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 1N.

Then he is given Q questions like that:

0 x y:change node xs 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.

1N,Q100000, the value A[i]N and A[i]100000

 

Input
In the first line there is a test number T.
(T3 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 N1 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
 

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 <iostream>
#include <cstdio>
#include <cstring>
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<int,int> 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<<w)<=i) w++;
		wid[i] = w - 1;
	}
	for(int i = 1; (1<<i) <= n; i++) {
		for(int j = 1; j + (1<<i) - 1 <= n; j++) {
			d[i][j] = depth[d[i-1][j]] < depth[d[i-1][j+(1<<(i-1))]] ? d[i-1][j] : d[i-1][j+(1<<(i-1))];
		}
	}
}
int LCA(int u,int v)
{
	u = pos[u];
	v = pos[v];
	if(u > v) swap(u,v);
	int k = wid[v-u+1];
	return depth[d[k][u]] < depth[d[k][v-(1<<k)+1]] ?

d[k][u] : d[k][v-(1<<k)+1]; } int seg[maxn<<2]; int ql,qr,x; void push_down(int o) { seg[o<<1] ^= seg[o]; seg[o<<1|1] ^= seg[o]; seg[o] = 0; } void Modify(int o,int L,int R) { if(ql<=L&&qr>=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 ", ans-1); } } } return 0; }





原文地址:https://www.cnblogs.com/lytwajue/p/7029120.html