本文主要是介绍Codeforces Global Round 18 D - X(or)-mas Tree(2-SAT)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原题

题目大意

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

这篇关于Codeforces Global Round 18 D - X(or)-mas Tree(2-SAT)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！