\(\textup{反色刷}\)
欧拉回路。
有解：每个点连接的黑边数为偶数
答案个数：连通块数
如果一个连通块内有两条路径，则可以在起点之间走两次，则它们一定可以合并成一条。
\(\textup{骑士游戏}\)
看起来很有让人 dp 的冲动。
假设可以用 dp。
\(f_u\) ：消灭 \(u\) 的最小代价。
\[f_u = \min \{f_u, s_u + \sum f_v(u\ to\ v) \} \]但是很容易发现这个 dp 有后效性，也不知道哪个点开始 。
那就把所有点扔进 SPFA 中跑。
\(f_u\) 的初值是 \(k_u\)。
\(\textup{[GXOI/GZOI2019] 旅行者}\)
喵喵
不是，这种东西是那个天才想出来的。
二进制分组。
根据二进制下每一位的数分别将节点分成两组。
一组作为原点，一组作为终点。
可以发现两个点一定会在不同集合至少一次。
也就是说，答案的起点和终点一定会在不同集合至少一次。
取每次跑最短路的之就行了。
\(\textup{「联合省选 2020 B」丁香之路}\)
如果往 \(i\) - \(s\) 见虚边，原问题相当于找 \(s\) 到 \(i\) 的一条欧拉回路，满足经过所有 \(m\) 条道路并且最短。
建出关键边和起点到终点的边，由于求欧拉回路，则必须满足全为偶点。
将奇点两两配对连边，由于边权是 \(|i - j|\)，那么如果要连边 \((u, v)\), 则连 \((u, u + 1),(u + 1, u + 2) ... (v - 1, v)\) 一定最优，因为欧拉回路也要满足联通，这么连能够多连几个点。
还剩没联通的很多连通块，则在这些连通块中求最小生成树即可，可行边只在相邻的连通块之间，边数其实为 \(n - 1\)。
对每个终点跑一边，复杂度为 \(\mathcal{O}(n ^ 2 \log n)\)。
\(\textup{Nastia Plays with a Tree}\)
发现切的顺序是没有影响的，到最后都是一堆链随便连。
考虑现在要切节点 \(u\)，节点 \(u\) 父亲是 \(f\)，节点 \(u\) 有 \(cnt\) 个子节点
-
\(cnt = 1\)，此时什么都不用做。
-
\(cnt = 2\)，发现当切掉 \((u, f)\) 后，剩下的就是一条链了。
-
\(cnt > 2\)，先切 \((u, f)\)，剩下再切 \(cnt - 2\) 刀。
为什么要切 \((u, f)\)，发现一个节点的子节点一定越少越好，当子节点数目到一就不用切了，所以切 \((u, f)\) 减少 \(f\) 的子节点个数。
\(\textup{Logical Operations on Tree}\)
用 or 边将整棵树分成很多连通块，发现最终点权为 \(1\) 要满足这些连通块中有至少一个块的值为 \(1\)。
考虑求出满足所有连通块中有至少一个块的值为 \(1\) 的方案数 ，正难则反，求所有连通块权全为 \(0\) 的方案数。
考虑 dp，设 \(f_{i, 0 / 1}\)：\(i\) 子树中，\(i\) 所在的连通块当前的值为 \(0/1\) 的方案数。
\[f_{i, 0} = f_{i, 0} * f_{j, 0} + f_{i, 1} * f_{j, 0} + f_{i, 0} * f_{j, 1}, \{i\ to\ j\} \]\[f_{i, 1} = f_{i, 1} * f_{j, 1}, \{i\ to\ j\} \]答案为 \(2 ^ {2 * n - 1} - f_{1, 0}\)
标签：textup,连通,欧拉,45,cnt,dp,Day44,节点,NOIP2024 From： https://www.cnblogs.com/lovely-sheep/p/18447634