自动搬运

查看原文

来自洛谷，原作者为

	SNiFe 但行好事，莫问前程

搬运于2025-08-24 21:37:30，当前版本为作者最后更新于2017-08-29 20:22:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题就是个简单的DFS，我不知道为什么各dalao要打lca，这道题就是在DFS中处理u，v到根节点的异或值，然后输出dis[u]^dis[v]就可以了（因为dis[tmp]^dis[tmp]^dis[u]^dis[v]=dis[u]^dis[v])；

我就上代码了：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include<cstring> 
using namespace std;
const int N=100005;
int n,m,k=0,head[N],dis[N];
bool visit[N];
struct node
{int to,next,w;}edge[N*2];
void add(int u,int v,int w)
{
    edge[++k].to=v;edge[k].next=head[u];edge[k].w=w;head[u]=k;
}
void dfs(int id,int val)
{
    dis[id]=val;visit[id]=true;
    for(int i=head[id];i;i=edge[i].next)
        if(!visit[edge[i].to])
            dfs(edge[i].to,val^edge[i].w);//处理异或值 
}
int main()
{
    scanf("%d",&n);
    int u,v,w;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);//建边 
    }
    dfs(1,0);scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        printf("%d\n",dis[u]^dis[v]);
    }
}