【bzoj1954】Pku3764 The xor-longest Path Trie树

题目描述

给定一棵n个点的带权树，求树上最长的异或和路径

输入

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.

输出

For each test case output the xor-length of the xor-longest path.

样例输入

4
1 2 3
2 3 4
2 4 6

样例输出

题解

Trie树

由于x^x=0，所以树上x和y之间路径的异或和 = x到根路径的异或和 xor y到根路径的异或和。

所以我们先对整棵树进行dfs，求出每个节点到根的路径异或和dis，并加入到Trie树。

然后枚举树上的节点，在Trie树中贪心查询与它异或和最大的数，并加到答案中即可。

#include <cstdio>

#include <algorithm>

#define N 100010

using namespace std;

int head[N] , to[N << 1] , len[N << 1] , next[N << 1] , cnt , v[N] , c[N * 30][2] , tot;

void add(int x , int y , int z)

{

	to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt;

}

void dfs(int x , int fa)

{

	int i;

	for(i = head[x] ; i ; i = next[i])

		if(to[i] != fa)

			v[to[i]] = v[x] ^ len[i] , dfs(to[i] , x);

}

void insert(int x)

{

	int i , p = 0;

	bool t;

	for(i = 1 << 30 ; i ; i >>= 1)

	{

		t = x & i;

		if(!c[p][t]) c[p][t] = ++tot;

		p = c[p][t];

	}

}

int query(int x)

{

	int i , p = 0 , ans = 0;

	bool t;

	for(i = 1 << 30 ; i ; i >>= 1)

	{

		t = x & i;

		if(c[p][t ^ 1]) ans += i , p = c[p][t ^ 1];

		else p = c[p][t];

	}

	return ans;

}

int main()

{

	int n , i , x , y , z , ans = 0;

	scanf("%d" , &n);

	for(i = 1 ; i < n ; i ++ ) scanf("%d%d%d" , &x , &y , &z) , add(x , y , z) , add(y , x , z);

	dfs(1 , 0);

	for(i = 1 ; i <= n ; i ++ ) insert(v[i]);

	for(i = 1 ; i <= n ; i ++ ) ans = max(ans , query(v[i]));

	printf("%d\n" , ans);

	return 0;

}

巴特西

【bzoj1954】Pku3764 The xor-longest Path Trie树

最新文章

热门文章