首页 > 其他 > 详细

P2420 让我们异或吧

时间:2018-07-07 23:15:00      阅读:251      评论:0      收藏:0      [点我收藏+]

传送门

做题背景(啥子?这个东西还能有背景?)最近同学在讲lca

在树上跑倍增的时候用一个类似于st表的东西,跟着倍增数组一起维护就行了。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=101000;
struct node
{
    int point;
    int weight;
    int nxt;
};
node line[maxn<<1];
int st[maxn][30];
int path[maxn][30];
int dep[maxn];
int head[maxn],tail;
void add(int a,int b,int c)
{
    line[++tail].point=b;
    line[tail].weight=c;
    line[tail].nxt=head[a];
    head[a]=tail;
}
void dfs(int now,int fa)
{
    dep[now]=dep[fa]+1;
    st[now][0]=fa;
    for(int i=1;(1<<i)<=dep[now];i++)
        st[now][i]=st[st[now][i-1]][i-1],path[now][i]=path[st[now][i-1]][i-1]^path[now][i-1];
    for(int i=head[now];i;i=line[i].nxt)
        if(line[i].point!=fa)
            path[line[i].point][0]=line[i].weight,dfs(line[i].point,now);
    return ;
}
int lca(int a,int b)
{
    int res=0;
    if(dep[a]<dep[b])   swap(a,b);
    for(int i=20;i>=0;i--)
        if(dep[st[a][i]]>=dep[b])
            res^=path[a][i],a=st[a][i];
    if(a==b)    return res;
    for(int i=20;i>=0;i--)
        if(st[a][i]!=st[b][i])
        {
            res^=(path[a][i]^path[b][i]);
            a=st[a][i];
            b=st[b][i];
        }
    return res^path[a][0]^path[b][0];
}
int main()
{
    int n,m;
    scanf("%d",&n);
    int a,b,c;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,0);
    /*for(int i=1;i<=5;i++)
    {
        for(int j=0;j<=4;j++)
            printf("%d ",path[i][j]);
        printf("\n");
    }*/
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }
}

P2420 让我们异或吧

原文:https://www.cnblogs.com/Lance1ot/p/9278754.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!