【poj3764】The xor-longest Path

2015.01.26 19:52 Mon | 12次阅读 | 旧日oi | 固定链接 | 源码

Description
In an edge-weighted tree, the xor-length of a path p is defined as the xor sum of the weights of edges on p:
_{xor}length(p)=\oplus_{e \in p}w(e)⊕ is the xor operator.
We say a path the xor-longest path if it has the largest xor-length. Given an edge-weighted tree with n nodes, can you find the xor-longest path?
Input
The input contains several test cases. The first line of each test case contains an integer n(1<=n<=100000), The following n-1 lines each contains three integers u(0 <= u < n),v(0 <= v < n),w(0 <= w < 2^31), which means there is an edge between node u and v of length w.
Output
For each test case output the xor-length of the xor-longest path.
Sample Input
4
0 1 3
1 2 4
1 3 6
Sample Output
7
题解
题意就是在树上求最大异或和
直接做n^2一定tle,所以考虑按位操作
先dfs一遍求出每个节点到根的距离的异或和
依次把每个节点插入字典树,由高位到低位
搜索的时候贪心查找就行了

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<iomanip>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdlib>
#include<deque>
#define maxn 100005
#define maxm 0
#define mod 100007
#define eps 1e-10
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long
using namespace std;
int val[maxn];
int n,x,y,w,mx,cnt;
struct edge{
    int to;
    int next;
    int val;
}e[maxn<<1];
struct trie{
    int next[2];
}t[maxn<<8];
int h[maxn],tp;
bool vis[maxn];
void ae(int u,int v,int w)
{
    tp++;
    e[tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp;
}
void Init()
{
    for(int i=0;i<n;i++) h[i]=vis[i]=0;
    t[0].next[0]=t[0].next[1]=0;
    tp=0;
    mx=0;
    cnt=0;
}
void dfs(int u,int w)
{
    vis[u]=1;
    val[u]=w;
    for(int v,i=h[u];i;i=e[i].next)
    {
        v=e[i].to;
        if(vis[v]) continue;
        dfs(v,w^e[i].val);
    }
}
void ins(int x)
{
    int now,p=0;
    for(int i=30;i>=0;i--)
    {
        now=x&(1<<i)?1:0;
        if(!t[p].next[now])
        {
            t[p].next[now]=++cnt;
            t[cnt].next[0]=t[cnt].next[1]=0;
        }
        p=t[p].next[now];
    }
}
int find(int x)
{
    int now,p=0,w=0;
    for(int i=30;i>=0;i--)
    {
        now=x&(1<<i)?0:1;
        if(t[p].next[now])
        {
            w|=1<<i;
            p=t[p].next[now];
        }
        else p=t[p].next[!now];
    }
    return w;
}
int main()
{
    while(cin>>n)
    {
        Init();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            ae(x,y,w);
            ae(y,x,w);
        }
        dfs(0,0);
        for(int i=0;i<n;i++)
        ins(val[i]);
        for(int i=0;i<n;i++)
        mx=max(mx,find(val[i]));
        printf("%d\n",mx);
    }
}```