CF1615D X(or)-mas Tree
\(Link\)
题意：给定一棵 \(n\) 个点的无根树，每条边有边权。若边权为 \(-1\) 则边权暂定。
然后有 \(m\) 条限制条件，每个条件给出形式为 \((u,v,w)\)，表示将 \(u\) 到 \(v\) 最短路径上的边权异或起来，用二进制写出后 \(1\) 的个数的奇偶性。
然后构造一种方案，把所有边权确定下来，要求满足所有限制。
（碎碎念：赛时没看到\(1\) 的个数的奇偶性，还以为是憨憨题，然后就GG惹。。。）
\(Solution:\)
首先我们能发现一个性质：
\[popcount(x \oplus y) \equiv popcount(x) \oplus popcount(y)\ (\text{mod}\ 2) \]挺易证的吧应该。
然后我们钦定 \(1\) 是根。
设 \(a_i\) 为从 \(1\) 到 \(i\) 的路径上异或起来的值的 \(popcount\)。
于是对于每组 \((u,v,w)\)，\(w\) 就等于 \(a_u \oplus a_v\)。
然后对于原有的有边权的边 \((U,V,W)\)，可以看做是另一条限制 \((U,V,popcount(W)\mod 2)\)
现在我们吧这些限制当做一张无向图的边，则我们现在要给图上的每个点 \(i\) 赋一个点权（即 \(a_i\)）。满足对于所有边 \(（u,v,w）\)，\(a_u \oplus a_v =w\)。
于是我们从 \(1\) 开始（因为 \(a_1\) 一定是 \(0\)）dfs 染色，遇到冲突了就是不行。
然后对于每条原来那棵树上的每条边 \((u,v)\)，如果有边权就输出边权，要么输出 \(a_u \oplus a_v\)。
\(Code:\)
// Problem: D. X(or)-mas Tree
// Contest: Codeforces Global Round 18
// URL: https://codeforces.com/contest/1615/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: jimmyywang
//
#include
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;i++)
#define wt int tt=d;while(tt--)
#define py puts("YES")
#define pn puts("NO")
#define fe(i,e) for(int i=0;i
inline ll rd() {
ll x=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c))x=x*10+c-'0',c=getchar();
return x*f;
}
#define d rd()
#define pb push_back
const ll N=600010;
struct edge{ll v,w,nx;}e[N<<1];
ll hd[N],cnt=1;
void add(ll u,ll v,ll w){e[++cnt]=(edge){v,w,hd[u]};hd[u]=cnt;}
ll qp(ll a,ll b,ll p){
ll ans=1;while(b){
if(b&1)ans=ans*a%p;
a=a*a%p;b>>=1;
}return ans;
}ll t,n,m;
vector > ee[200010];
struct node{
ll x,y,z;
}a[200010];
bool now[200010];
bool vis[200010];
bool flg;
#define mp make_pair
#define pop __builtin_popcount
void dfs(ll u,ll fa,ll p){if(flg)return;
now[u]=p;vis[u]=1;
for(int i=hd[u];i;i=e[i].nx){
ll v=e[i].v;if(v==fa)continue;
if(vis[v]){
if((now[v]^now[u])!=e[i].w){flg=1;return;}
continue;
}dfs(v,u,p^e[i].w);
}
}void Dfs(ll u,ll fa){
fe(i,ee[u]){
ll v=ee[u][i].first;
if(v==fa)continue;
printf("%lld %lld ",u,v);
if(ee[u][i].second==-1)printf("%lld\n",now[u]^now[v]);
else printf("%lld\n",ee[u][i].second);
Dfs(v,u);
}
}
int main(){
wt{
n=d,m=d;
f(i,1,n)hd[i]=0,ee[i].clear();cnt=1;
f(i,1,n-1){
ll u=d,v=d,w=d;
ee[u].pb(mp(v,w)),ee[v].pb(mp(u,w));
if(w!=-1)add(u,v,(bool)(pop(w)&1)),add(v,u,(bool)(pop(w)&1));
}f(i,1,m){
ll u=d,v=d,w=d;
add(u,v,w),add(v,u,w);
}
f(i,1,n)now[i]=vis[i]=0;flg=0;
f(i,1,n)if(!vis[i])dfs(i,0,0);
if(flg){pn;continue;}
py;Dfs(1,0);
}
return 0;
}