Luogu4551 最长异或路径

tony102

2021 年 05 月 29 日

1616 次浏览

暂无评论

567字数

题解

[Link](https://www.luogu.com.cn/problem/P4551)

## Sol

01 Trie 入门题

类似于在树上求路径和的方法,路径 $(u,v)$ 异或和也可以拆成 $u$ 到树根和树根到 $v$ 两段. **只要是满足结合律的性质的运算都可以这么做.**

要让两段异或起来的值最大, 也就是尽可能地选 $1$. 并且高位上的 $1$ 要优先于低位上的 $1$. 所以,首先预处理所有节点到根路径上的异或和, 把它们插到 01 Trie 上, 然后询问每一个异或和, 如果那一位与 $1$ 异或存在一个 $1$ ,那么就要先选.比较所有的最大值即可.

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1e6 + 5;

int n, num, tot;
int head[SIZE], f[SIZE], ch[SIZE][2];

struct node {
	int to, v, nxt;
} edge[SIZE << 1];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

void addEdge(int u, int v, int d) {
	edge[++ num] = (node) {v, d, head[u]}, head[u] = num;
}

void insert(int x) {
	int p = 1;
	for (int i = 30; ~i; -- i) {
		int opt = (x >> i) & 1;
		if (!ch[p][opt]) ch[p][opt] = ++ tot;
		p = ch[p][opt];
	}
}

int query(int x) {
	int p = 1, res = 0;
	for (int i = 30; ~i; -- i) {
		int opt = (x >> i) & 1;
		if (ch[p][opt ^ 1]) p = ch[p][opt ^ 1], res |= (1 << i); 
		else p = ch[p][opt];
	}
	return res;
}

void dfs(int u, int fa) {
	for (int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (v == fa) continue;
		f[v] = f[u] ^ edge[i].v; dfs(v, u);
	}
}

int main() {
	n = read(), tot = 1;
	for (int i = 1, u, v, d; i < n; ++ i) {
		u = read(), v = read(), d = read();
		addEdge(u, v, d), addEdge(v, u, d);
	}
	dfs(1, 0); int mx = 0;
	for (int i = 1; i <= n; ++ i) insert(f[i]);
	for (int i = 1; i <= n; ++ i) mx = std::max(mx, query(f[i]));
	printf("%d\n", mx);
	return 0;
}
```

最后修改：2021 年 09 月 07 日