在非常良好的精神状态下写出来的,样例过了,测评全WA求条
查看原帖
在非常良好的精神状态下写出来的,样例过了,测评全WA求条
923248
Lian_zy楼主2024/4/14 09:53
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 10;
struct node {
	int u, v;
	node(int x, int y) : u(x), v(y) {} ;
};
vector<node> G[maxn];
int n, m, u, v, w, c[maxn], d[maxn], lg[maxn], fa[maxn][20];
void dfs(int u, int f) {
	fa[u][0] = f;
	d[u] = d[f] + 1;
	for (int j = 1; j <= lg[d[u] - 1]; j++) fa[u][j] = fa[fa[u][j - 1]][j - 1];
	for (auto it : G[u]) {
		v = it.u, w = it.v;
		if (v == f) continue;
		c[v] = c[u] ^ w;
		dfs(v, u);
	}
	return ;
}
int LCA(int x, int y) {
	if (d[x] < d[y]) swap(x, y);
	while (d[x] > d[y]) x = fa[x][lg[d[x] - d[y]]];
	if (x == y) return x;
	for (int j = lg[d[u] - 1]; j; j--) {
		if (fa[x][j] == fa[y][j]) continue;
		x = fa[x][j];
		y = fa[y][j]; 
	}
	return fa[x][0];
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		scanf("%d %d %d", &u, &v, &w);
		lg[i + 1] = lg[i + 1 >> 1] + 1;
		G[u].push_back(node(v, w));
		G[v].push_back(node(u, w));
	}
	dfs(1, 0);
	scanf("%d", &m);
	while (m--) {
		scanf("%d %d", &u, &v);
		w = LCA(u, v);
		printf("%d\n", c[u] ^ c[w] ^ c[v] ^ c[fa[w][0]]);
	}
	return 0;
}
2024/4/14 09:53
加载中...