C++(g++ 7.5.0) 解法, 执行用时: 401ms, 内存消耗: 7468K, 提交时间: 2023-07-30 17:56:20

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int arr[N];
int dis[N];
vector<int>v[N];
int f[N][22];
int de[N];
void dfs(int fa, int u, int val) {
    dis[u] = val ^ arr[u];
    for (auto it : v[u]) {
        if (it == fa)continue;
            f[it][0]=u;
         de[it]=de[u]+1;
        for(int i=1;i<=20;i++){
            f[it][i]=f[f[it][i-1]][i-1];
        }
        dfs(u, it, val ^ arr[u]);
    }
}
int lca(int a,int b){
    if(de[a]<de[b])swap(a,b);
    for(int i=20;i>=0;i--){
        if(de[f[a][i]]>=de[b])a=f[a][i];
    }  
    if(a==b)return a;
    for(int i=20;i>=0;i--){
        if(f[a][i]!=f[b][i]){
            a=f[a][i];b=f[b][i];
        }
    }
    return f[a][0];
}
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    de[1]=1;
    dfs(-1, 1, 0);
    int q; cin >> q;
    while (q--) {
        int x, y; cin >> x >> y;
        cout << (dis[x] ^ dis[y] ^ arr[lca(x,y)]) << "\n";
    }

    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 197ms, 内存消耗: 7308K, 提交时间: 2020-01-20 11:56:30

#include <bits/stdc++.h>

constexpr int maxn = 1e5 + 5;

int dep[maxn],Fa[maxn][21],w[maxn],a[maxn],n,q;
std::vector<int>G[maxn];

void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;
    Fa[u][0]=fa;
    a[u]=a[fa]^w[u];
    for(int i=1;(1<<i)<=dep[u];i++) Fa[u][i]=Fa[Fa[u][i-1]][i-1];
    for(auto &v:G[u]){if(v==fa) continue;dfs(v,u);}
}
int lca(int x,int y)
{
    if(dep[x]<dep[y]) std::swap(x,y);
    for(int i=20;i>=0;i--) if((1<<i)<=dep[x]-dep[y]) x=Fa[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(Fa[x][i]!=Fa[y][i]) x=Fa[x][i],y=Fa[y][i];
    return Fa[x][0];
}
int main()
{
#ifdef LOCAL
	freopen("input.in","r",stdin);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	dfs(1,0);
	scanf("%d",&q);
	while(q--)
	{
		int x,y;scanf("%d%d",&x,&y);
		printf("%d\n",a[x]^a[y]^a[lca(x,y)]^a[Fa[lca(x,y)][0]]);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 162ms, 内存消耗: 7264K, 提交时间: 2020-01-20 20:25:44

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5+100;
int a[maxn],d[maxn],dep[maxn];
int f[maxn][20];
vector<int>G[maxn];
void dfs(int u,int fa)
{
	f[u][0] = fa;
	dep[u] = dep[fa] + 1;
	for(int i=1;i<=19;i++)f[u][i] = f[f[u][i-1]][i-1];
	for(auto v : G[u])
	{
		if(v == fa)continue;
		d[v] = d[u]^a[v];
		dfs(v,u);
	}
}

int lca(int u,int v)
{
	if(dep[u] < dep[v])swap(u,v);

	for(int i=19;i>=0;i--)
		if(dep[f[u][i]] >= dep[v])u = f[u][i];

	if(u == v)return u;

	for(int i=19;i>=0;i--)
	if(f[u][i] != f[v][i])u=f[u][i],v=f[v][i];

	return f[u][0];

}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	d[1] = a[1];
	dfs(1,0);
	int m;
	cin>>m;
	while(m--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		int ans = d[u]^d[v]^a[lca(u,v)];
		cout<<ans<<'\n';
	}
}