c/c++语言开发共享skkyk:题解 洛谷P2420 【让我们异或吧】lca+xor前缀和

刚学了lca,写篇题解巩固一下

首先题目有误: （a是否是男生 ）xor（ b是否是男生）＝a和b是否能够成为情侣，这句话显然是错误的qwq

对于这道题,容易看出,对于待处理的两个点，只要我们找到他的最近公共祖先,问题便游刃而解了

所以我的思路就是：lca+xor前缀和

这是我的大法师函数

yihuo数组就是保存当前节点到根节点的xor值

推算了一下，对于xor前缀和有: 两个点x,y间的的xor值=yihuo[x]^yihuo[y]

void dfs(int f,int father,int xor) {     depth[f]=depth[father]+1;     fa[f][0]=father;     yihuo[f]=xor;     for(int i=1;(1<<i)<=depth[f];i++)         fa[f][i]=fa[fa[f][i-1]][i-1];     for(int i=head[f];i;i=edge[i].next)         if(edge[i].to!=father)             dfs(edge[i].to,f,xor^edge[i].dis); }

剩下的就是普通的lca，在深层节点向上跳的每个过程中

记录下待求的ans

具体实现见代码

#include<iostream> #include<cstdio> using namespace std; int n,m,cnt,ans; #define n 100000+1 int fa[n][22]; struct node {     int next,to,dis; } edge[n<<1]; int head[n],yihuo[n],lg[n],depth[n],a[n]; inline void add(int from,int to,int dis) {     edge[++cnt].to=to;     edge[cnt].next=head[from];     edge[cnt].dis=dis;     head[from]=cnt; } void dfs(int f,int father,int xor) {     depth[f]=depth[father]+1;     fa[f][0]=father;     yihuo[f]=xor;     for(int i=1; (1<<i)<=depth[f]; i++)         fa[f][i]=fa[fa[f][i-1]][i-1];     for(int i=head[f]; i; i=edge[i].next)         if(edge[i].to!=father)             dfs(edge[i].to,f,xor^edge[i].dis); } void lca(int x,int y) {     if(depth[x]<depth[y])         swap(x,y);     while(depth[x]>depth[y]) {         ans=ans xor yihuo[x] xor yihuo[fa[x][lg[depth[x]-depth[y]]-1]];         x=fa[x][lg[depth[x]-depth[y]]-1];     }     if(x==y)         return ;     for(int i=lg[x]-1; i>=0; i--) {         if(fa[x][i]!=fa[y][i]) {             ans=ans xor yihuo[x] xor yihuo[fa[x][i]];             ans=ans xor yihuo[y] xor yihuo[fa[y][i]];             x=fa[x][i],y=fa[y][i];         }     }     ans=ans xor yihuo[x] xor yihuo[y] ; } int main() {     scanf("%d",&n);     for(int i=1; i<=n-1; i++) {         int u,v,dis;         scanf("%d%d%d",&u,&v,&dis);         add(u,v,dis),add(v,u,dis);     }     for(int i=1; i<=n; i++)         lg[i]=lg[i>>1]+1;     dfs(1,0,0);     scanf("%d",&m);     for(int i=1,x,y; i<=m; i++) {         ans=0;         scanf("%d%d",&x,&y);         lca(x,y);         printf("%dn",ans);     }     return 0; }

留个赞再走吧qwq