【bzoj1954】Pku3764 The xor-longest Path

2015.06.12 19:53 Fri | 21次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给定一颗边权树,求任意两个点之间的路径权值的最大异或和 n<=100000

题解

处理出每个点到根的异或和dis[i],然后根据异或的性质,i,j之间的异或和等于dis[i]^dis[j],所以把数都扔到Trie树里贪心就行了。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100005
int n,m;
struct edge
{
    int to,next,val;
}e[N<<1];
int h[N],tp;
void ae(int u,int v,int w)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp;
}
int dis[N],ans;
int son[N*40][2],cnt;
void dfs(int u,int f)
{
    int i;
    for(i=h[u];e[i].to;i=e[i].next)
    if(e[i].to!=f) 
    {
        dis[e[i].to]=dis[u]^e[i].val;
        dfs(e[i].to,u);
    }
}
void insert(int x)
{
    int rt=0,tmp;
    for(int i=31;i>=0;i--)
    {
        tmp=(x&(1<<i))?1:0;
        if(!son[rt][tmp]) son[rt][tmp]=++cnt;
        rt=son[rt][tmp];
    }
}
int get_ans(int x)
{
    int rt=0,tmp,ret=0;
    for(int i=31;i>=0;i--)
    {
        tmp=(x&(1<<i))?0:1;
        if(son[rt][tmp]) ret|=(1<<i),rt=son[rt][tmp];
        else rt=son[rt][tmp^1];
    }
    return ret;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {   
        memset(h,0,sizeof(h));tp=0;cnt=0;ans=0;
        memset(son,0,sizeof(son));
        for(int u,v,w,i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            ae(u,v,w);ae(v,u,w);
        }
        dfs(1,0);
        for(int i=1;i<=n;i++) insert(dis[i]);
        for(int i=1;i<=n;i++) ans=max(ans,get_ans(dis[i]));
        printf("%d\n",ans);
    }
}```