「题解」AGC052B Tree Edges XOR

do_while_true · 2022-11-05 10:04:48 · 题解

考虑边权转点权，让边权满足其为相邻点权的异或和，操作变成交换两个点的点权。

随便钦定一个为根，设 d_i 为初始时 i 的点权，f_i 是 i 期望得到为多少。如果存在 d,f，满足它们是相同的集合，就有解。

注意到如果确定了一个点的点权，那么其他所有点权都能唯一的确定。

现在钦定 f_i 为 i 到根路径上的边权和（或者说钦定 f_1=0），注意到任何一组解都能把所有点权异或 f_1，得到 f_1=0 的解，所以判断是否有解就判断 f_1=0 的时候是否有解。

现在 f 确定了，看是否存在 d，满足 d 和 f 是相同的集合。

现在继续钦定 d_i 为 i 到根路径上边权和，与 f 相同，所有可能为答案的 d' 都是 d 异或上一个 x 得到的。

那么有解的必要条件就是 (d_1\oplus x)\oplus (d_2\oplus x)\oplus...\oplus (d_n\oplus x)=f_1\oplus f_2\oplus...\oplus f_n，由于 n 为奇数，所以可以解出 x 是多少。

由于这仅是必要条件，那么最后还要 \text{check} 一下是否合法。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define pb emplace_back
#define mp std::make_pair
#define fi first
#define se second
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef std::vector<int> vi;
typedef std::vector<ll> vll;
const ll mod = 998244353;
ll Add(ll x, ll y) { return (x+y>=mod) ? (x+y-mod) : (x+y); }
ll Mul(ll x, ll y) { return x * y % mod; }
ll Mod(ll x) { return x < 0 ? (x + mod) : (x >= mod ? (x-mod) : x); }
ll cadd(ll &x, ll y) { return x = (x+y>=mod) ? (x+y-mod) : (x+y); }
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T>
T &read(T &r) {
    r = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
    while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
    return r = w ? -r : r;
}
const int N = 100010;
int n, ent, head[N];
int d[N], f[N];
struct Edge {
    int next, to, v1, v2;
}e[N << 1];
inline void add(int x, int y, int w1, int w2) {
    e[++ent].to = y; e[ent].next = head[x]; e[ent].v1 = w1; e[ent].v2 = w2; head[x] = ent;
}
void dfs(int x, int fa, int h1, int h2) {
    d[x] = h1; f[x] = h2;
    for(int i = head[x]; i; i = e[i].next) {
        int v = e[i].to; if(v == fa) continue ;
        dfs(v, x, h1 ^ e[i].v1, h2 ^ e[i].v2);
    }
}
signed main() {
    read(n);
    for(int i = 1; i < n; ++i) {
        int u, v, w1, w2; read(u); read(v); read(w1); read(w2);
        add(u, v, w1, w2);
        add(v, u, w1, w2);
    }
    dfs(1, 0, 0, 0);
    int x = 0;
    for(int i = 1; i <= n; ++i) x ^= f[i] ^ d[i];
    for(int i = 1; i <= n; ++i) d[i] ^= x;
    std::sort(d + 1, d + n + 1);
    std::sort(f + 1, f + n + 1);
    for(int i = 1; i <= n; ++i)
        if(f[i] != d[i]) {
            puts("NO");
            return 0;
        }
    puts("YES");
    return 0;
}