原题链接

题解

给定若干条路径限制，问是否合法

对于树上任意三个点 \(a,b,c\) （不一定直接相连），如果已知 \(a\oplus b,b\oplus c\) 那么 \(a\oplus c\) 也已知

所以我们可以对限制里相连的节点放到一个集合里，并且统一记录他们到集合头领的路径异或值

由于奇数个1异或偶数个1之间的异或和10异或的规则一样，所以我们用1代替奇数个1的异或值，0代替偶数个1的异或值

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=114514;

int fa[2*N];
int yh[2*N]={0};
int x[2*N],y[2*N],c[2*N];

int finds(int now)
{
    int f=fa[now];
    if(f==now) return now;
    int root=finds(f);
    yh[now]^=yh[f];
    return fa[now]=root;
}

bool flag=1;

void add(int a,int b,int v)
{
    int fx=finds(a),fy=finds(b);

    if(fx==fy)
    {
        if((yh[a]^yh[b])!=v) flag=0;
    }
    else
    {
        fa[fx]=fy;
        yh[fx]=yh[a]^yh[b]^v;
    }
}

void solve()
{
    int n,q;
    cin>>n>>q;

    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        yh[i]=0;
    }
    for(int i=1;i<n;i++)
    {
        cin>>x[i]>>y[i]>>c[i];

        if(c[i]!=-1) add(x[i],y[i],__builtin_popcount(c[i]) % 2);
    }

    while(q--)
    {
        int a,b,v;
        cin>>a>>b>>v;

        add(a,b,v);
    }
    if(!flag) cout<<"no\n";
    else
    {
        cout<<"yes\n";
        for(int i=1;i<n;i++)
        {
            if(c[i]!=-1)
            {
                cout<<x[i]<<' '<<y[i]<<' '<<c[i]<<'\n';
            }
            else
            {
                if(finds(x[i])==finds(y[i]))   cout<<x[i]<<' '<<y[i]<<' '<<(yh[x[i]]^yh[y[i]])<<'\n';
                else
                {
                    cout<<x[i]<<' '<<y[i]<<" 0\n";//这里的值是任意的，合并集合是为了让之后的没有限制的边的取值不产生矛盾;hack:所有边都是-1
                    add(x[i],y[i],0);
                }
            }
        }
    }
    flag=1;

}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}