The xor-longest Path(01字典树)

题目链接

http://poj.org/problem?id=3764

题意

有一个树,路径的权值是路径上所有边的异或值,求权值最大的路径。

思路

将根节点到某一节点的异或加到01字典树中,然后在字典树中查询 与 根节点到某一节点的异或值 异或的最大值。

如何保证异或出来的最大值是树上的一段连续路径?
1、两条路径有相交部分,相交部分一异或就抵消了,剩下的是连续路径。
2、没有相交部分,但是两条路径有一个共同点根,根会将两条路径连成一条路径。

代码

#include 
#include 
#include 

using namespace std;

#define ll long long
const int N=100005;
struct node
{
    int to,w,next;
}e[N*20];
int head[N],cnt;
int tot;
int val[N*33],ch[N*33][2];
ll ans=0;

void init()
{
    tot=cnt=0;
    memset(head,-1,sizeof(head));
    ch[0][0]=ch[0][1]=0;
    ans=0;
}

void add(int u,int v,int w)
{
    e[cnt]=node{v,w,head[u]};
    head[u]=cnt++;
}

void insert(ll x)
{
    int u=0;
    for(int i=32;i>=0;i--)
    {
        int v=(x>>i)&1;
        if(!ch[u][v])
        {
            ch[tot][0]=ch[tot][1]=0;
            val[tot]=0;
            ch[u][v]=tot++;
        }
        u=ch[u][v];
    }
    val[u]=x;
}

ll query(ll x)
{
    int u=0;
    for(int i=32;i>=0;i--)
    {
        int v=(x>>i)&1;
        if(ch[u][v^1])
        {
            u=ch[u][v^1];
        }
        else u=ch[u][v];
    }
    return x^val[u];
}

void dfs(int x,int pre,int data)
{
    insert(data);
    for(int i=head[x];i!=-1;i=e[i].next)
    {
        int to=e[i].to;
        int w=e[i].w;
        if(to!=pre)
        {
            ans=max(ans,query(data^w));
            dfs(to,x,data^w);
        }
    }
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        init();
        for(int i=1;i<n;i++)
        {
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        dfs(1,-1,0);
        printf("%lld\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注