[AGC052B] Tree Edges XOR 题解

题目链接

点击打开链接

题目解法

怎么感觉这场 \(B\) 比 \(C\) 思维量更大
考虑一步很妙的操作：把边权变成点权，以达到简化操作的目的
使每条边的边权为两端点的异或和，手画一下可以发现，操作简化成了交换两端点的点权

我们定义 \(d_{1/2,i}\) 定义为在 \(1/2\) 树上，\(i\) 到根的权值异或和
不难得到合法的必要条件是在所有的 \(d_{1,i}\oplus Delta\) 之后，\(d_1\) 和 \(d_2\) 这两个集合相等（如果直接用一开始的权值，而不用到根的权值异或和也能做，且做法基本相同）
因为点数为奇数，所以不难求得 \(Delta\) 的值
上面得到的条件是必要条件，而不是充分条件，所以最后需要判断一下

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=100100;
int n,w[2][N];
int e[N<<1],ne[N<<1],h[N],idx;
int d[2][N];
void dfs(int u,int fa){
    for(int i=h[u];~i;i=ne[i]) if(e[i]!=fa){
        F(k,0,1) d[k][e[i]]=d[k][u]^w[k][i/2];
        dfs(e[i],u);
    }
}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
int main(){
    n=read();
    ms(h,-1);
    F(i,0,n-2){
        int x=read(),y=read();w[0][i]=read(),w[1][i]=read();
        add(x,y),add(y,x);
    }
    dfs(1,-1);
    int Delta=0;
    F(i,1,n) Delta^=d[0][i]^d[1][i];
    F(i,1,n) d[1][i]^=Delta;
    F(i,0,1) sort(d[i]+1,d[i]+n+1);
    F(i,1,n) if(d[0][i]!=d[1][i]){ puts("NO");exit(0);}
    puts("YES");
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}