【每日一题】7月30日题目精讲—Xor Path

Xor Path

https://ac.nowcoder.com/acm/problem/20857?&headNav=acm

https://ac.nowcoder.com/acm/problem/20857?&headNav=acm
思路:

 
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<bits/stdc++.h>
typedef long long ll;
ll gcd(ll a, ll b)
{
	return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
	return a * b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 7;
int qmi(int a, int k, int p)		//快速幂模板
{
	int res = 1;
	while (k)
	{
		if (k & 1) res = (ll)res * a % p;
		k >>= 1;
		a = (ll)a * a % p;
	}
	return res;
}
///////////////////////////////////////////////////////////
vector<int> a[N];
long long b[N], p[N], ans = 0;
int n;
void dfs(int x, int y) {
	p[x] = 1;
	long long sign = n - 1;
	for (int i = 0; i < a[x].size(); i++) {
		int son = a[x][i];
		if (son == y)
			continue;
		dfs(son, x);
		sign += p[son] * (n - p[son]);
		p[x] += p[son];
	}
	sign += p[x] * (n - p[x]);
	sign = sign / 2;
	if (sign % 2)
		ans ^= b[x];
}
int main() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
		cin >> b[i];
	dfs(1, 0);
	cout << ans << endl;
	return 0;
}


awsl

全部评论

相关推荐

07-17 11:56
门头沟学院 Java
感谢东子的收留
熬夜脱发码农:无敌了,这是我看到第二个京东的提前批大佬了我还在畏畏缩缩准备八股算法
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务