[数据结构与算法]P2420 让我们异或吧(dfs)

让我们异或吧 - 洛谷https://www.luogu.com.cn/problem/P2420

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <unordered_map>
#include <cmath>
#include <map>
#include <cctype>
#include <cstdlib>
#include <deque>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1000010;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) ((x)&(-x))

int head[MAXN];
int nxt[MAXN];
int ver[MAXN];
int cost[MAXN];
int cnt;
int d[MAXN];

inline void add(int x, int y, int c) {
	ver[++cnt] = y;
	cost[cnt] = c;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

void dfs(int now, int fa, int val) {
	d[now] = val;
	for (int i = head[now]; i; i = nxt[i]) {
		int y = ver[i];
		int c = cost[i];
		if (y != fa)
			dfs(y, now, val ^ c);
	}
}

int main() {
	int n;
	int x, y, c;
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		scanf("%d %d %d", &x, &y, &c);
		add(x, y, c);
		add(y, x, c);
	}
	dfs(1, 0, 0);
	int m;
	scanf("%d", &m);
	while (m--) {
		scanf("%d %d", &x, &y);
		printf("%d\n", d[x]^d[y]);
	}
	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖