题目大意
给你一棵无根树,部分边边权未知。 给了两点,知道其简单路径边权的异或和的二进制中1的个数的奇偶性(以下简称奇偶性),求这棵树的所有边的边权。存在无解,输出No
题解
很容易证明二进制下奇数个1异或奇数个1为偶数个1,偶数个1异或偶数个1为偶数个1,奇数个1异或偶数个1为奇数个1。然后待求的边权就可以为0或1了
显然需把边的约束条件转换到点的约束条件。但无法知道点的奇偶性,所以假定点的奇偶性
设 f[i]
为i到根的路径的异或和,
根据XOR的性质,两点的简单路径的异或和等于其到根的路径的异或和的异或。s=f[u]|f[v] //s为u,v简单路径的异或和
已知u,v间路径异或和的奇偶性,根据此关系建边,将u,v连通,构建连通图,维护连通性。当v为奇数的点和v为偶数的点连通时,对于其他点来说,他们存在一条异或和又奇又偶的简单路径至v,不合法。
当知道待求路径的两端端点的奇偶性的连通关系时,即可以得知带权路径的边权。
#include<cstdio>
#include<iostream>
#include<algorithm>
#define maxn 200005
struct Edge{
int u,v,w;
}ed[maxn];
int fa[maxn*2];
int getfa(int x){
if(fa[x]!=x)
return fa[x]=getfa(fa[x]);
return x;
}
void merge(int x,int y){
int fx=getfa(x);int fy=getfa(y);
fa[fy]=fx;
return;
}
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
for(int i=1;i<=2*n;i++)
fa[i]=i;
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
int tmp=w;
if(w>=0){
w=__builtin_parity(w);
if(w==0){
merge(u+n,v+n);
merge(u,v);
}
else{
merge(u,v+n);
merge(u+n,v);
}
}
ed[i]={u,v,tmp};
}
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
if(w==0){
merge(u+n,v+n);
merge(u,v);
}
else{
merge(u,v+n);
merge(u+n,v);
}
}
bool f=1;
for(int i=1;i<=n;i++){
if(getfa(i)==getfa(i+n)){
cout<<"NO"<<endl;
f=0;
break;
}
if(getfa(i)!=getfa(1)&&getfa(i+n)!=getfa(1)){
merge(i,1);
merge(i+n,1+n);
}
}
if(f==0){
continue;
}
cout<<"YES"<<endl;
for(int i=1;i<n;i++){
int u,v,w;
u=ed[i].u;v=ed[i].v;w=ed[i].w;
if(w==-1)
w=(getfa(u)!=getfa(v));
cout<<u<<' '<<v<<' '<<w<<endl;
}
}
}