POJ3764 The xor-longest Path

发表于 | 分类于 |
字数统计: 471 字

题目地址

题解

求出从根出发到每一个点的异或距离，然后问题转化为在这些距离中找两个异或值最大的。
这是个经典问题，只需要在用trie树查询时进行反向行走即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>          
#include <cstdlib>        
#include <cstring> 
#include <algorithm>
using namespace std;
typedef unsigned int ll;
struct Tree{
    int l,r;
    Tree(){l=r=-1;}
};
typedef struct{
    int v,_next; 
    ll cost;
}Edge;
Edge edge[200005];
int cnt=0,at[100005]; 
void addedge(int _u,int _v,ll _cost){
    edge[cnt].v=_v,
    edge[cnt].cost=_cost,
    edge[cnt]._next=at[_u],
    at[_u]=cnt++;
} 
int n,siz=1;
Tree tr[3000005];
ll vx[100005];
bool vis[100005];
void Trie_insert(ll num){
    //printf("%u\n",num); 
    for(ll j=(1<<31),cur=0;j;j>>=1)
        if((j&num)==0){//l:0 r:1
            if(tr[cur].l<0)
                tr[cur].l=siz++;
            cur=tr[cur].l;
        }else{
            if(tr[cur].r<0)
                tr[cur].r=siz++;
            cur=tr[cur].r;
        }
}
ll Trie_search(ll x){
    ll res=0;
    for(ll j=1<<31,cur=0;j;j>>=1){
        if(x&j){
            if(tr[cur].l>0)res+=j,cur=tr[cur].l;
            else cur=tr[cur].r;
        }else{
            if(tr[cur].r>0)res+=j,cur=tr[cur].r;
            else cur=tr[cur].l;
        }
    }
    return res;
}
void dfs(int cur,ll val){
    for(int i=at[cur];i!=-1;i=edge[i]._next){
        int _v=edge[i].v;
        if(!vis[_v])
            vis[_v]=1,
            vx[_v]=val^edge[i].cost,
            Trie_insert(vx[_v]),
            dfs(_v,vx[_v]);
    }
}
int main(){
    while(~scanf("%d",&n)){
    	for(int i=0;i<siz;i++)
    		tr[i].l=tr[i].r=-1;
        siz=1,cnt=0;
        memset(at,-1,sizeof(at));
        memset(vis,0,sizeof(vis));
        int u,v;ll c;
        for(int i=0;i<n-1;i++)
            scanf("%d%d%u",&u,&v,&c),
            addedge(u,v,c),
            addedge(v,u,c);
        dfs(0,0);
        vx[0]=0;
        //Trie_insert(0u);
        ll ans=0;
        for(int i=0;i<n;i++)
            ans=max(ans,Trie_search(vx[i]));
        printf("%u\n",ans);
    }
    return 0;      
}

Powered By Valine
v1.5.2