luogu2420

思路:

非常裸的一道lca的题，维护一个lca数组，一个异或数组，然后在找lca的过程中。进行异或即可。

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=100000+1000,logN=20;
int lca[N][logN+5],Xor[N][logN+5],a[N];
struct node
{
    int v,nxt,w;
}e[N*2];
int ejs,head[N];
void add(int u,int v,int w) {
    e[++ejs].v=v;e[ejs].w=w;e[ejs].nxt=head[u];head[u]=ejs;
}
int n,dep[N];
void dfs(int u,int father) {
    for(int i=1;i<=logN;++i) {
        lca[u][i]=lca[lca[u][i-1]][i-1];
        Xor[u][i]=Xor[lca[u][i-1]][i-1]^Xor[u][i-1];
        if(lca[u][i]==0) break;
    }
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(v==father) continue;
        dep[v]=dep[u]+1;
        lca[v][0]=u;
        Xor[v][0]=e[i].w;
        dfs(v,u);
    }
}
int LCA(int x,int y) {
    if(dep[x]>dep[y]) swap(x,y);
    int ans=0;
    for(int i=logN-1;i>=0;--i) {
        if(dep[lca[y][i]]>=dep[x]) {
            ans^=Xor[y][i];
            y=lca[y][i];
        }
    }
    for(int i=logN-1;i>=0;--i) {
        if(lca[x][i]!=lca[y][i]) {
            ans^=Xor[x][i];
            ans^=Xor[y][i];
            x=lca[x][i];
            y=lca[y][i];
        }
    }
    if(x!=y) {
        ans^=Xor[x][0]^Xor[y][0];
    }
    return ans;

}
int main() {
    scanf("%d",&n);
    for(int i=1;i<n;++i) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dep[0]=-1;
    dfs(1,0);
    int m;
    scanf("%d",&m);
    while(m--) {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",LCA(x,y));
    }
    return 0;
}