原题
给你一棵无根树,部分边边权未知。 给了两点,知道其简单路径边权的异或和的二进制中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; } } }