POJ 3764 The Xor-longest Path 题解

 

原题地址：原题戳我

---

把这题模型转换一下， 对于任意一条路径的异或和，可表示为f(u,v)，则f(u,v)=f(1,u)^f(1,v)，通过dfs遍历每个点，我们可以预处理f[1]-f[i]，复杂度为O(n)，所以问题就转化成了在一个数组内，找两个数异或值最大，这样子我们就可以用0/1trie来维护每个数。

---

同时题目要求我们最后的异或和最大，那我们可以选择从最高位开始进行建trie，然后两数在二进制下的每一位尽量不同，如果实在不行，我们就只能沿着相同的0或1继续寻找，用一种类似贪心的路径选择直接找出答案。

---

 

代码如下QWQ:

 

#include<cctype>
#include<cstdio>
#include<cstring>
#define max(a,b) ((a)>(b)? (a):(b))
using namespace std;
int read()
{
    int x=0,w=0;
    char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
    return w? -x:x;
}
const int N=2e5+10;
struct edge{
    int v,next,w;
}e[N<<1];
struct Trie_Tree{
    int next[2];
    void clear(){memset(next,0,sizeof(next));}
}t[N<<5];
bool vis[N<<5];
int len=-1,linkk[N<<1];
void insert(int u,int v,int w)
{
    e[++len].next=linkk[u],linkk[u]=len,e[len].v=v,e[len].w=w;
    e[++len].next=linkk[v],linkk[v]=len,e[len].v=u,e[len].w=w;
}
int n,cnt,ans,val[N<<5];
void reset()
{
    memset(linkk,-1,sizeof(linkk));
    memset(vis,0,sizeof(vis));
    len=-1,cnt=0,ans=0;
}
void dfs(int u,int v)
{
    val[u]=v,vis[u]=1;
    for(register int i=linkk[u];~i;i=e[i].next)
    {
        int to=e[i].v;
        if(vis[to]) continue;
        dfs(to,v^e[i].w);
    }
}
void add_trie(int x)
{
    int u=0,p=0;
    for(register int i=30;~i;--i)
    {
        if(x&(1<<i)) p=1;
        else p=0;
        if(!t[u].next[p])
        {
            t[u].next[p]=++cnt;
            t[cnt].clear();
        }
        u=t[u].next[p];
    }
}
int trie(int x)
{
    int u=0,num=0,p=0;
    for(register int i=30;~i;--i)
    {
        if(x&(1<<i)) p=0;
        else p=1;
        if(t[u].next[p]) 
        {
            num|=(1<<i);
            u=t[u].next[p];
        }
        else u=t[u].next[p^1];
    }
    return num;
}
int main()
{
    while(~scanf("%d",&n))
    {
        reset();
        for(register int u,v,w,i=1;i<n;++i)
        {
            u=read()+1,v=read()+1,w=read();
            insert(u,v,w);
        }
        t[cnt].clear();
        dfs(1,0);
        for(int i=1;i<=n;++i)
        {
            ans=max(ans,trie(val[i]));
            add_trie(val[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}