这种异或和问题一看就是线性基对吧。。。

要维护的是树上两点之间的路径,所以考虑倍增。

发现可以记\(p_{i,j}\)为\(i\)到\(i\)的\(2^j\)次父亲(不含)的点权构出的线性基。

于是我们需要合并两个线性基,记这个操作为\(Merge(p1,p2)\)。

则\(p_{i,j}=Merge(p_{i,j-1},P_{f_{i,j-1},j-1})\)

如何实现?

其实很简单,枚举其中一个线性基中的元素,按照之前构建线性基的方法加入另一个线性基即可。

然后...做完了?!

时间复杂度\(O(qlog^2a_ilogn)\),而且读入/输出的数字规模较大,消耗的时间较多,所以你需要读优。

可能还需要氧气

code:

#include
    
     using namespace std;int n,q,u,v,vis[20010],f[20010][20],dep[20010],pr[20],sz;long long g[20010],p[20010][20][65],P[65],ans;vector
     
      e[20010];void scan(long long &x){    char c=getchar();    x=0;    while('0'>c||c>'9')c=getchar();    while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();}void scan(int &x){    char c=getchar();    x=0;    while('0'>c||c>'9')c=getchar();    while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();}void print(long long x){    sz=0;    while(x)pr[++sz]=x%10,x/=10;    while(sz)putchar(pr[sz--]+'0');}void Push(long long x,long long *pp){    if(!x)return;    for(int i=60;i>=0;i--){        if(x&(1ll<
      
       =0;i--)mp[i]=p1[i];    for(int i=60;i>=0;i--)Push(p2[i],mp);}void Merge2(long long *p1,long long *mp){    for(int i=60;i>=0;i--)Push(p1[i],mp);}void dfs(int x){    vis[x]=1;    for(int i=0;i
       
        =0;i--)if(dep[x]-(1<
        
         =dep[y])Merge2(p[x][i],P),x=f[x][i];    for(int i=15;i>=0;i--)if(f[x][i]!=f[y][i])Merge2(p[x][i],P),x=f[x][i],Merge2(p[y][i],P),y=f[y][i];    if(x!=y)Push(g[x],P),Push(g[y],P),Push(g[f[x][0]],P);    else Push(g[x],P);}int main(){    scan(n),scan(q);    for(int i=1;i<=n;i++)scan(g[i]),Push(g[i],p[i][0]);    for(int i=1;i
         
          =0;i--)(ans^P[i])>ans?ans^=P[i]:0; print(ans),putchar('\n'); } return 0;}