Loading...

洛谷P4551 最长异或路径

check评论:0 条 remove_red_eye浏览量:416 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-29

这种异或路径问题,我们一般用$trie$树解答

因为$a\ xor\ a=0$,所以如果一条边算两次异或还是$0$,我们就可以先算出根节点到每个点的路径的异或长度,然后两条路径长度异或起来就是两点间异或长度,我们用$trie$树来维护每个点到根的异或,用贪心的思想,如果这一为是$1$我们就找$0$,是$0$就找$1$,就可以了qwq

#include <bits/stdc++.h>
using namespace std;
int xo[100010],ch[3000010][2],head[100010],cnt,n,tot;
struct edge
{
    int next,to,dis;
}e[200020];
void add(int u,int v,int dis)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=dis;
    head[u]=cnt;
}
void dfs(int u,int fa)
{
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa)
        {
            continue;
        }
        xo[v]=xo[u]^e[i].dis;
        dfs(v,u);
    }
}
void ins(int x)
{
    int rt=0;
    for(int i=(1<<30);i;i>>=1)
    {
        int c=(i&x)?1:0;
        if(!ch[rt][c])
        {
            ch[rt][c]=++tot;
        }
        rt=ch[rt][c];
    }
}
int query(int x)
{
    int rt=0,ans=0;
    for(int i=(1<<30);i;i>>=1)
    {
        int c=(i&x)?1:0;
        if(ch[rt][c^1])
        {
            ans+=i;
            rt=ch[rt][c^1];
        }
        else
        {
            rt=ch[rt][c];
        }
    }
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
    {
        ins(xo[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,query(xo[i]));
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名