题目概述

给出一棵 $n​$ 个节点的树，每个节点有权值，一条路径上的对称数定义为最小的出现次数为偶数（包括 $0​$ ）的数，现在给出 $m​$ 个询问 $(x,y)​$ 表示询问 $(x,y)​$ 路径上的对称数。

解题报告

奇数次偶数次想到异或，我们先给每个权值配对上一个随机数，然后求出路径上的异或值(主席树)，就可以得到这条路径上的权值信息。不过这样还是没法做，但是我们发现这样可以判断一段权值范围内是否均为奇数次。

所以考虑二分 $mid$ ，验证 $[1,mid]$ 是否存在偶数次（不是均为奇数次）就行了。

如果你用二分+主席树查询，效率为 $O(mlog_2^2n)$ ，然后你就会成功TLE……正确姿势是在主席树上二分，其实也不难理解，就是验证 $mid$ 然后往左走或者往右走，这样就是 $O(mlog_2n)$ 了。

ps：有一种特殊数据：树退化成链，且链上权值涵盖所有权值，这样就会导致在主席树上无法查找到答案，所以主席树右边界要多开 $1$ ，没有注意到导致我WA了若干发TAT。

示例程序

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int maxn=200000,maxa=200001,maxt=1e7,Log=18;

int te,n,m,a[maxn+5],fa[maxn+5][Log+5],dep[maxn+5];ULL ha[maxa+5],pre[maxa+5];
int E,lnk[maxn+5],nxt[(maxn<<1)+5],son[(maxn<<1)+5],lca;
int len,ro[maxn+5],ls[maxt+5],rs[maxt+5];ULL sum[maxt+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
inline ULL Rand(){
    static ULL now;now=((ULL)rand()<<48)+((ULL)rand()<<32)+((ULL)rand()<<16)+rand();
    now+=((ULL)(rand()&1)<<47)+((ULL)(rand()&1)<<31)+((ULL)(rand()&1)<<15);return now;
}
#define Add(x,y) son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E
#define newnode(l,r,s) (ls[len]=(l),rs[len]=(r),sum[len]=(s),len++)
int Build(int L,int R){
    int now=newnode(0,0,0);if (L==R) return now;int mid=L+(R-L>>1);
    ls[now]=Build(L,mid);rs[now]=Build(mid+1,R);return now;
}
int Insert(int p,int pos,ULL k,int l=1,int r=maxa){
    int now=newnode(ls[p],rs[p],sum[p]^k);if (l==r) return now;int mid=l+(r-l>>1);
    if (pos<=mid) ls[now]=Insert(ls[p],pos,k,l,mid); else rs[now]=Insert(rs[p],pos,k,mid+1,r);return now;
}
int Find(int A,int B,ULL SA=0,ULL SB=0,int l=1,int r=maxa){
    if (l==r) return l;int mid=l+(r-l>>1);ULL now=SA^sum[ls[A]]^SB^sum[ls[B]]^(a[lca]>mid?0:ha[a[lca]]);
    if (now^pre[mid]) return Find(ls[A],ls[B],SA,SB,l,mid);
    return Find(rs[A],rs[B],SA^sum[ls[A]],SB^sum[ls[B]],mid+1,r);
}
void Dfs(int x,int pre=0){
    ro[x]=Insert(ro[pre],a[x],ha[a[x]]);fa[x][0]=pre;dep[x]=dep[pre]+1;
    for (int j=1;j<=Log;j++) fa[x][j]=fa[fa[x][j-1]][j-1];
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);
}
inline int LCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    for (int j=Log;~j&&dep[x]>dep[y];j--) if (dep[fa[x][j]]>=dep[y]) x=fa[x][j];
    if (x==y) return x;
    for (int j=Log;~j;j--) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
    return fa[x][0];
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    srand(19260817);for (int i=1;i<=200000;i++) ha[i]=Rand(),pre[i]=pre[i-1]^ha[i];
    for (readi(te);te;te--){
        len=0;E=0;memset(lnk,0,sizeof(lnk));
        readi(n);readi(m);for (int i=1;i<=n;i++) readi(a[i]);
        for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
        ro[0]=Build(1,maxa);Dfs(1);
        for (int t=1,x,y;t<=m;t++){
            readi(x);readi(y);lca=LCA(x,y);
            printf("%d\n",Find(ro[x],ro[y]));
        }
    }
    return 0;
}