luogu#P11170. 「CMOI R1」图上交互题 / Constructive Minimum Xor Path

    ID: 15095 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>数学图论2024洛谷原创Special JudgeO2优化构造Ad-hoc

「CMOI R1」图上交互题 / Constructive Minimum Xor Path

题目背景

2024 年 1 月 13 日 15:59:31,随着最后一发交互 J 题的提交出现了 Wrong Answer,小 G 的 EC-Final 比赛结束了,也意味着在 ICPC 生涯中第一次打铁。

痛定思痛,小 G 决定批量生产交互题给自己做。如何批量生产交互题?只要在一个数据结构中有若干个未知量 aia_i,每次询问给定向量 xx,交互库会返回关于 aia_i 的函数 f(x)f(x),这样就能批量生产交互题了!

那为什么这题并不是交互题呢。

题目描述

给定一个 nn 个点,mm 条边的无向图。第 ii 条边 (ui,vi)(u_i,v_i) 有一个未知边权 aia_i

对于任何一条路径,定义其代价如下:设路径为 (p0,p1,...,pk)(p_0,p_1,...,p_k),其中要求 (pi1,pi)(p_{i-1},p_i) 是无向图中的边,设其为第 eie_i 条边。那么路径的代价即为 i=1kaei\bigoplus\limits_{i=1}^{k} a_{e_i}。其中 \bigoplus 表示异或。(该路径可以经过重复点和重复边,即 ppee 可以包含重复的数)

定义 f(x,y)f(x,y) 为从 xxyy 的所有路径中代价的最小值。特别地,当 x=yx=y 时,f(x,y)=0f(x,y)=0

给定 n,mn,m,再对于每条边 (ui,vi)(u_i,v_i) 给定 f(ui,vi)f(u_i,v_i),你需要求出是否存在一组合法的 aia_i,如果有解,你还需要构造一组解。

输入格式

第一行两个正整数 n,mn,m

2m+12\sim m+1 行每行两个正整数 ui,viu_i,v_i 和一个非负整数 f(ui,vi)f(u_i,v_i)

请注意:本题并不保证图连通;可能会存在重边和自环。

输出格式

如果不存在解,则仅输出 No

否则,在第一行输出 Yes,在第二行输出 mm 个非负整数 aia_i 表示一组合法的解。

答案可能有很多组,此时输出任意一组解即可。你需要保证 输出的 0ai<2630\le a_i<2^{63}

3 3
1 2 2
2 3 3
3 1 1
Yes
2 3 114514
1 1
1 1 1
No

提示

样例解释

答案输出的图如下:

考虑 f(1,2)f(1,2)

  • 考虑路径 121\rightarrow 2,路径的代价为 22

  • 考虑路径 $1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2$,路径的代价为 231145142=1145132\oplus3\oplus114514\oplus2=114513

此外还存在其他路径,但可以证明不存在代价比 22 更小的路径,故 f(1,2)=2f(1,2)=2

数据范围

本题采用捆绑测试。

Subtask\text{Subtask} 特殊性质 分数
11 保证有解 2020
22 mn+10m\le n+10 3030
33 5050

对于 100%100\% 的数据,1n,m5×1051\le n,m\le 5\times 10^51ui,vin1\le u_i,v_i\le n0f(ui,vi)<2310\le f(u_i,v_i)<2^{31}