CF1788F XOR, Tree, and Queries
边权转点权+染色+构造
首先对于限制，可以转化。设 \(f_u\) 表示 \(1\) 到 \(u\) 的异或和，那么限制 \((u,v,w)\) 就可以表示为 \(f_u\oplus f_v=w\)。也就意味这如果我们将限制 \((u,v,w)\) 连边，要考虑的就变成 \(f_u\) 的赋值问题。这一步将边权转为点权。
接下来考虑如何判断无解。显然连边之后构成了若干连通块。分开考虑，如果按照连通块上的任意生成树构造一组合法解，那么只需要判断非树边的边权是否合法即可（也就是判断环上异或和是否为 \(0\)）。
在有解的基础上，如何构造最优解？在上面的遍历中，我们已经构造出了一组解（\(f_u\) 的赋值已经确定）。观察答案在 \(f_u\) 上的体现，发现 \(f_u\) 对答案有贡献的条件是在原树上的度数为奇数，我们称这样的 \(u\) 为关键点。在连通块中，一个点的赋值可以确定所有点，并且等价于同时异或 \(x\)，如果关键点为偶数，那么无论如何修改赋值都无法改变答案；否则存在一个构造使得答案为 \(0\)，即将该连通块中的点都异或当前 \(ans\)。
复杂度 \(O(n)\)。
还有一种劣优解，这里也讲一下。我们可以套路的按位考虑，那么判无解就成了 \(01\) 染色；同样按位考虑构造最优解，若连通块中关键点为偶数，并且关键点 \(01\) 数量差值为 \(1\)，那么全体异或可以交换 \(01\) 数量，由此得到更优解。
复杂度 \(O(n\log V)\)。
下面是 \(O(n)\) 代码。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 2.5e5 + 10;
int n, q, sum, flg = 1, ans;
int d[N], vis[N], deg[N];
std::vector<pii> e[N];
void dfs(int u, int fa) {
if(deg[u] & 1) sum++;
vis[u] = 1;
for(auto v : e[u]) {
if(v.fi == fa) continue;
if(vis[v.fi] && d[v.fi] ^ d[u] ^ v.se) {
flg = 0;
}
else if(!vis[v.fi]) {
d[v.fi] = d[u] ^ v.se;
dfs(v.fi, u);
}
}
}
struct node {
int u, v;
} a[N];
void dfs2(int u, int fa) {
vis[u] = 1;
d[u] = d[u] ^ ans;
for(auto v : e[u]) {
if(v.fi == fa) continue;
if(!vis[v.fi]) dfs2(v.fi, u);
}
}
void Solve() {
std::cin >> n >> q;
for(int i = 1; i < n; i++) {
std::cin >> a[i].u >> a[i].v;
deg[a[i].u]++, deg[a[i].v]++;
}
for(int i = 1; i <= q; i++) {
int u, v, w;
std::cin >> u >> v >> w;
e[u].pb({v, w}), e[v].pb({u, w});
}
int ok = 0;
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
sum = 0;
dfs(i, 0);
if(!flg) {
std::cout << "No\n";
return;
}
if(sum & 1) ok = i;
}
}
std::cout << "Yes\n";
for(int i = 1; i < n; i++) ans = ans ^ (d[a[i].u] ^ d[a[i].v]);
if(ok) {
memset(vis, 0, sizeof(vis));
dfs2(ok, 0);
}
for(int i = 1; i < n; i++) {
std::cout << (d[a[i].u] ^ d[a[i].v]) << " \n"[i == n - 1];
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}