CF1788F 做题记录

· · 个人记录

分析

几个小 trick 的巧妙结合，想到之后思路就很自然了。

  1. 用树上差分的套路，把 x 的点权 a_x 记为根到 x 的最短路径上边的异或和，这样一方面可以用 a_x \bigoplus a_y 表示 x 到 y 的路径异或和，另一方面可以用相邻两个点的点权异或表示一条边的权值，很方便。

  2. 尝试转化限制，建一张新无向图 G^{\prime} ，其中对每个 a_x \bigoplus a_y =d 的限制连一条 x 到 y 权值为 d 的无向边，对每个连通块随意找一个点开始 dfs，便可以确定连通块内每个点的权值，如果有两条路径确定的某个点权值不一样就判作无解。

  3. 满足异或和最小的限制。设全部边权异或和为 S1，容易发现只有原树上度数为奇数的点才会对 S1 的值产生贡献，于是把这些点标记。设标记点权值异或异或和为 S2，若不为 0，可找到一个连通块满足其中标记点的个数为奇数，把连通块内每个点的权值异或 S2 即可；若找不到，表明每个连通块产生的影响是固定的，异或和不变，故直接输出即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 250010;
const int M = 500010;
int n, m;
int head[N], pre[M], ver[M], tot, w[M];
void add(int x,int y,int z){
    ver[++tot]=y; pre[tot]=head[x]; head[x]=tot; w[tot]=z;
}
struct edge{
    int x,y;
}e[M];
int dg[N], siz[N], col[N];
bool vis[N];
int f[N];
int main(){
    cin>>n>>m;
    for (int i=1;i<n;++i){
        int x,y;cin>>x>>y;
        e[i].x=x; e[i].y=y;
        dg[x]++; dg[y]++;
    }
    for (int i=1;i<=m;++i){
        int x,y,z;cin>>x>>y>>z;
        add(x,y,z); add(y,x,z);
    }
    queue<int> q;
    int ans=0;
    for (int j=1;j<=n;++j){
        if (vis[j]) continue;
        q.push(j);
        f[j]=0; vis[j]=1;
        while(q.size()){
            int x=q.front(); q.pop();
            col[x]=j;
            if (dg[x]&1) {
                ans^=f[x];
                siz[j]++;
            }
            for (int i=head[x]; i; i=pre[i]){
                int v=ver[i];
                if (vis[v]){
                    if (f[v]!=(f[x]^w[i])){
                        puts("NO");
                        return 0;
                    }
                }
                else {
                    f[v]=(f[x]^w[i]); vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    for (int i=1;i<=n;++i){
        if (siz[i]&1){
            for (int j=1;j<=n;++j){
                if (col[j]==i) f[j]^=ans;
            }
            break;
        }
    }
    puts("YES");
    for (int i=1;i<n;++i){
        printf("%d ",f[e[i].x]^f[e[i].y]);
    }
    return 0;
}