[异或 + 主席树] BZOJ5361 [Lydsy1805月赛]对称数

容易想到异或的套路,给每个权值分配一个随机大权值。

然后在权值线段树上二分就好啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>
typedef unsigned long long uLL;
using namespace std;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<3)+(res<<1)+ch-'0', ch=gc();
return res*ff;
}
const int maxn=200005,maxe=maxn*2;
int N_seg,ch[maxn*40][2],rt[maxn],a[maxn],b[maxn],N=200000;
int fir[maxn],nxt[maxe],son[maxe],tot;
uLL Xor[maxn*40],rdm[maxn];
inline void maintain(int p){
Xor[p]=Xor[ch[p][0]]^Xor[ch[p][1]];
}
inline int newnode(){
N_seg++; ch[N_seg][0]=ch[N_seg][1]=Xor[N_seg]=0;
return N_seg;
}
int Build(int L,int R,int k){
int p=newnode();
if(L==R){ if(k) Xor[p]=rdm[L]; return p; }
int mid=(L+R)>>1;
ch[p][0]=Build(L,mid,k); ch[p][1]=Build(mid+1,R,k);
maintain(p); return p;
}
int Update(int pre,int L,int R,int pos){
int p=newnode(); Xor[p]=Xor[pre]; ch[p][0]=ch[pre][0]; ch[ p][1]=ch[pre][1];
if(L==R){ Xor[p]^=rdm[pos]; return p; }
int mid=(L+R)>>1;
if(pos<=mid) ch[p][0]=Update(ch[p][0],L,mid,pos);
else ch[p][1]=Update(ch[p][1],mid+1,R,pos);
maintain(p); return p;
}
int Query(int p1,int p2,int p3,int al,int L,int R){
if((Xor[p1]^Xor[p2]^(L<=al&&al<=R?rdm[al]:0))==Xor[p3]) return N+1;
if(L==R) return L;
int mid=(L+R)>>1;
int t=Query(ch[p1][0],ch[p2][0],ch[p3][0],al,L,mid);
if(t==N+1) t=Query(ch[p1][1],ch[p2][1],ch[p3][1],al,mid+1,R);
return t;
}
inline uLL getrdm(){
return ( ( ((uLL)rand()<<15) + (uLL)rand() ) << 15 ) + ( ((uLL)rand()<<15) + (uLL)rand() );
}
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int anc[maxn][20],dep[maxn];
void dfs_info(int x,int pre){
anc[x][0]=pre;
for(int i=1;i<=18;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=pre){
rt[son[j]]=Update(rt[x],1,N,a[son[j]]);
dep[son[j]]=dep[x]+1; dfs_info(son[j],x);
}
}
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int t=dep[x]-dep[y],i=0;i<=18;i++) if((t>>i)&1) x=anc[x][i];
if(x==y) return x;
for(int i=18;i>=0;i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i], y=anc[y][i];
return anc[x][0];
}
int n,Q,_test;
int main(){
srand(2333);
N=200000; for(int i=1;i<=N;i++) rdm[i]=getrdm();
_test=getint();
while(_test--){
N_seg=0;
memset(fir,0,sizeof(fir)); tot=0;
n=getint(); Q=getint();
for(int i=1;i<=n;i++) a[i]=getint();
for(int i=1;i<=n-1;i++){
int x=getint(),y=getint();
add(x,y); add(y,x);
}
rt[n+1]=Build(1,N,1);
rt[0]=Build(1,N,0); rt[1]=Update(rt[0],1,N,a[1]);
dfs_info(1,1);
while(Q--){
int x=getint(),y=getint(),lca=LCA(x,y);
printf("%d\n",Query(rt[x],rt[y],rt[n+1],a[lca],1,N));
}
}
return 0;
}