题意简述
一棵树大小为 $n$（偶数）。将点两两配对，一对的权值为两点在树上的距离。求方案时使所有对的权值和为 $K$。
$n\le 10^5$，需判断无解。
主要思路
为缩短公式长度，定义 $M_2(x) = x \bmod 2$，$u, v$ 间匹配为 $m(u, v)$，某个方案得到的答案为 $S$。
设一条边 $e$ 将树分成两部分，其中节点数较少的为 $w_e$。
不难发现，至少有 $M_2(w_e)$，至多有 $w_e$ 个匹配经过 $e$。
所以对于一棵树 $T$，答案的下上界就分别是 $L(T) = \sum\limits_e M_2(w_e), R(T) = \sum\limits_e w_e$。
又注意到 $S=\sum\limits_{m(u, v)}(\operatorname{dep}(u) + \operatorname{dep}(v) - 2\operatorname{dep}(\operatorname{lca}(u ,v)))\equiv \sum\limits_{u\in[1, n]}\operatorname{dep}(u)\equiv R(T)\pmod{2}$，故 $K$ 与 $R(T)$ 奇偶性相同也是一个有解的必要条件。
（钦定根节点深度为 $0$。）
然后我们来证明这些就是有解的充分条件。
$n = 2$显然成立。考虑归纳，下证若在 $n = 2n’ - 2$ 时命题成立，考虑 $n = 2n’$。
首先我们取出一个重心 $G$，则此时 $\sum\limits_e w_e = \sum\limits_{i\neq G}\operatorname{siz}(i)$。
如果 $K = R(T)$，直接求出 dfs 序 $r_i$，将 $r_i$ 与 $r_{i+n/2}$ 匹配即可。（这里运用了一下移位技巧。）
否则，取 $G$ 的儿子 $g$ 使 $\operatorname{siz}(g)$ 最大。此时显然有 $\operatorname{siz}(g) \ge 2$（否则为上一种情况）。
取节点 $w$ 为子树 $g$ 中深度最大且 $\operatorname{siz}(w)\ge 2$ 的节点。
此时，如果 $K + 2\operatorname{dep}(w) > R(T)$，必然存在 $g$ 子树中的一个非叶节点 $u$ 使 $K + 2\operatorname{dep}(u) = R(T)$，匹配 $u$ 与 $u$ 的任意一个儿子，对其他点按照上面情况的移位技巧即可。
否则即 $K + 2\operatorname{dep}(w) \le R(T)$。
- 如果 $w$ 有两个或以上儿子 $u, v$，匹配并在树中删除它们，得到新树 $T’$。
显然它们都是叶子节点，故 $K’ = K - 2, L(T’) = L(T) - 2, R(T’) = R(T) - 2(\operatorname{dep}(w) + 1)$。
并且，此时 $T’$ 重心仍为 $G$，节点数减少 $2$，且 $K’\in[L(T’), R(T’)]$，故根据归纳假设有解。 - 如果 $w$ 只有一个儿子 $u$，匹配 $w, u$ 并删除它们，得到新树 $T’$。
同理易得$K’ = K - 1, L(T’) = L(T) - 1, R(T’) = R(T) - 2\operatorname{dep}(w) - 1$。
重心不变，节点数减少 $2$，根据归纳假设有解。
由此，我们证明了上述条件为有解的充要条件。
考虑如何构造，发现直接以重心为根，根据上述证明充分性的过程模拟即可。
由于操作的特殊性，复杂度可以做到 $O(n)$，但本人懒得动脑就直接写了个 $O(n\log n)$ 的。
参考代码
1 |
|