CF1394D Boboniu and Jianghu
容易发现若 \(b_u \ne b_v\) 则边的方向确定，问题转化为给 \(b_u = b_v\) 的边定向。
设 \(f_{u, 0/1}\) 为 \(u\) 连向父亲的点的方向是 \(u \to fa\) 还是 \(fa \to u\)。我们知道一个点的贡献系数是 \(\max(in, out)\)，其中 \(in\) 和 \(out\) 为入边和出边个数。然后我们先假设儿子全部选 \(f_{v, 0}\)，然后贪心地选择贡献小的调整为 \(f_{v, 1}\) 即可。
LOJ6669 Nauuo and Binary Tree
考虑先问一遍 \(1, i\) 得到每个点的深度。
考虑按深度从小到大确定每个点的父亲。先对上一层及以上的点树剖，然后维护一个 \(y\) 初始为 \(1\)，设 \(y\) 的重链底为 \(z\)，询问 \(\operatorname{dis}(x, z)\) 可知道 \(\operatorname{lca}(x, z)\) 的深度，我们知道 \(x\) 一定在异于 \(z\) 的一棵子树，于是递归下去即可。
P7565 [JOISC 2021 Day3] ビーバーの会合 2
容易将问题转化为，选择一条最长的链，使得这条链两端子树大小 \(\ge \frac{j}{2}\)。
点分治，每次统计跨过重心的路径的贡献，维护后缀 \(\max\) 即可。
CF830E Perpetual Motion Machine
分类讨论。
如果有多个连通块，对于一个连通块如果有解，那么可以将别的点设为 \(0\)。于是问题转化为一个连通块的情况。
- 有环一定可以，把环上的 \(d\) 改成 \(1\)。
- 有度 \(\ge 4\) 的点，构造 \((2, 1, 1, 1, 1)\) 即可。
- 有两个度 \(= 3\) 的点，容易发现把路径上的点缩成一个大点后与度 \(= 4\) 的情况本质相同，把两点路径上的点改成 \(2\)，其他儿子改成 \(1\)。
- 没有度 \(\ge 3\) 的点，此时树退化成链，根据基本不等式可证明无解。
- 恰好有一个度 \(= 3\) 的点，此时树的形状一定是一个点挂着三条链。打表发现三条链的长度 \(\ge (2, 2, 2)\) 或 \((1, 3, 3)\) 或 \((1, 1, 5)\)（其中 \(\ge\) 是三维偏序）有解，否则无解。
CF1514E Baby Ehab's Hyper Apartment
考虑竞赛图的一些性质。可以证明它一定有至少一条哈密顿路径。
于是我们增量构造哈密顿路径，考虑已经构造了一条 \([1, i - 1]\) 的哈密顿路径，增加 \(i\) 这个点，每次容易二分找到 \(a_k \to i \to a_{k + 1}\)，将它插入即可。
找到哈密顿路径之后，考虑按拓扑序构造所有强连通分量。可以证明竞赛图中强连通分量缩点之后，拓扑序小的点与每一个拓扑序比它大的点都有连边，方向是小连向大（否则它们就能进一步缩点了）。我们每次问 \(a_i\) 与 \(a_1, a_2, \cdots, a_{i - 1}\) 有没有出边，如果有那么 \(a_i\) 和 \(a_{i - 1}\) 一定在同一个强连通分量，把它们合并即可。
标签：连通,哈密顿,20230703,拓扑,路径,讲题,ge,即可 From： https://www.cnblogs.com/zltzlt-blog/p/17522890.html