欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

skkyk:题解 洛谷P2420 【让我们异或吧】lca+xor前缀和

程序员文章站 2022-03-20 17:20:45
刚学了LCA,写篇题解巩固一下 首先题目有误: (A是否是男生 )xor( B是否是男生)=A和B是否能够成为情侣 ,~~这句话显然是错误的qwq~~ 对于这道题,容易看出,对于待处理的两个点,只要我们找到他的最近公共祖先,问题便游刃而解了 所以我的思路就是: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("%d\n",ans);
    }
    return 0;
}

留个赞再走吧qwq