Tang-Dreamoon's Blog

poj 3764

发表于 | 分类于 ， ，

路径异或和最大

　　题目链接：poj 3764

　　题意：给定一棵 N≤10^5 个点的树，每条边上有一个权值，求出一条路径使得路径上的边权异或和尽可能的大。

　　题解：这个题最终是要求出一条路径，使得它的边权异或和最大。因为这是一棵树，所以每一条路径都是两个端点之间唯一的路径。这时，我突然联想到了求两点之间的路径长度，方法是 Root 到 X 的距离加上 Root 到 Y 的距离减去两倍的 Root 到 Lca 的距离。这道题有没有类似的方法呢？这时我们将惊喜的发现，因为两个相同的数异或值为零，所以如果直接将 Root 到 X 的异或和与 Root 到 Y 的异或和异或起来，Root 到 Lca 的异或和将会直接抵消掉！所以问题就转化为了，求出每一个点到根的异或和 Wi ，然后挑出两个 Wi 使得它们的异或和最大。所以我们就将每一个数看成一个二进制的零一串，插入 Trie 树，然后尽可能的走每一位的取反的边，所有取反边的和就是最后的答案。

　　我思故我在：垃圾 POj 卡我 Vector ！记着存边要用邻接表！

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define MAXN 212222  
using namespace std;
struct node {  
    int v, w, next;  
}edge[MAXN * 2];
int map[100100];
bool vis[100100];
int head[MAXN];  
int er[33];
char ap[50];
int love=0,e=0;
int from[6122222][2];
void addEdge(int u,int v,int w)  
{  
    edge[e].v=v;edge[e].next=head[u];edge[e].w=w;head[u]=e++;  
    edge[e].v=u;edge[e].next=head[v];edge[e].w=w;head[v]=e++;  
} 
inline int read()
{
	int t=0;
	char a=getchar();
	while(a<'0'||a>'9')a=getchar();
	while(a>='0'&&a<='9') t=t*10+a-'0',a=getchar();
	return t;
}
inline int max(int a,int b)
{
	return a > b ? a : b ;
}
void dfs(int u, int x) {  
    map[u] = x;
    for(int i = head[u]; i != -1; i = edge[i].next) {  
        int v = edge[i].v;  
        int w = edge[i].w;  
        if(!vis[v]) {
        	vis[v]=1;
            dfs(v, x ^ w);  
        }  
    }  
}
inline void make()
{
	er[0]=1;
	for(int i=1;i<=30;i++)
		er[i]=er[i-1]*2;
}
inline int ask()
{
	int tot=0,now=0;
	for(int i=0;i<=30;i++)
	{
		int x=(ap[i]-'0')^1;
		if(from[now][x]!=0)
			tot+=er[30-i],now=from[now][x];
		else
			now=from[now][x^1];
	}
	return tot;
}
inline void work()
{
	int now=0;
	for(int i=0;i<=30;i++)
	{
		int x=ap[i]-'0';
		if(from[now][x]!=0)
			now=from[now][x];
		else
			from[now][x]=++love,now=from[now][x],from[now][0]=from[now][1]=0;
	}
}
int main()
{
	make();
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int x, y, z; 
        e = 0;  
        memset(head, -1, sizeof(head));  
        for(int i = 1; i < n; i++) {  
            x=read(),y=read(),z=read(); 
            addEdge(x, y, z);  
        }
        from[0][0]=from[0][1]=0;
		love=0;
		map[0]=0;
		vis[0]=1;
        dfs(0,0);
		int ans=0;
		for(int j=30;j>=0;j--)
		{
			if(map[0]>=er[j])
			{
				map[0]-=er[j];
				ap[30-j]='1';
			}
			else ap[30-j]='0';
		}
		work();
		for(int i=1;i<n;i++)
		{
			for(int j=30;j>=0;j--)
			{
				if(map[i]>=er[j])
				{
					map[i]-=er[j];
					ap[30-j]='1';
				}
				else ap[30-j]='0';
			}
			ans=max(ans,ask());
			work();
		}
		printf("%d\n",ans);
		memset(vis,0,sizeof(vis));
	}
	return 0;
}