题解

思路

长度为 $2n-2$ 的闭合路线必须把每条树边恰好经过两次。选择每个内部节点的子节点访问顺序后，深度优先遍历就产生这样一条路线；反过来，任意最短路线也对应于这些子节点顺序。因此，一个子树中的全部叶子在环形访问顺序中连续出现。

设整棵树共有 $L$ 个叶子。两个指定叶子之间的两个开区间共包含 $L-2$ 个叶子。两边数量相等当且仅当 $L$ 为偶数，并且每一边都包含 $L/2-1$ 个叶子。若 $L$ 为奇数，可以立即回答 NO。

四个指定叶子分别位于根的四棵不同子树中。要让 $a,b$ 与 $c,d$ 都互为环上对点，四个叶子的循环顺序只能交错。将方向反转不会改变可行性，因此只需考虑顺序

于是需要同时满足：从 $a$ 到 $b$ 的半圈包含 $c$ 所在的整棵根子树而不包含 $d$ 所在的根子树；从 $c$ 到 $d$ 的半圈包含 $b$ 所在的整棵根子树而不包含 $a$ 所在的根子树。

做法

考虑端点为 $x,y$，要求包含指定叶子 $f$ 所在根子树、排除指定叶子 $g$ 所在根子树的半圈。

标记根到 $x$ 和根到 $y$ 的两条路径。对每个标记节点，凡是它的某个儿子未被标记，该儿子的整棵子树都可以作为一个独立块：调整子节点访问顺序时，这一块可以完整地放入半圈，也可以完整地放在另一半圈。所有其他叶子恰好被这些块划分。

令每个块的权值为其中的叶子数。$f$ 所在的根子树必须选，$g$ 所在的根子树必须不选。扣除必选块后，对其余块做子集和，判断能否恰好凑出 $L/2-1$。

分别执行以下两个判定：

• 端点为 $a,b$，必选 $c$ 所在根子树，排除 $d$ 所在根子树；
• 端点为 $c,d$，必选 $b$ 所在根子树，排除 $a$ 所在根子树。

若两次都可行，则可以按两个选择结果把根的普通子树交叉放入四个区间；四棵指定根子树内部的选择只影响各自相邻的区间，不会互相冲突。因此两次判定可以同时实现。反之，任何合法环形顺序都会为两次判定给出对应的块集合，所以条件也是必要的。

复杂度

子任务 1 中，可以递归枚举每个独立块选或不选，完成两次子集和判定。最坏时间复杂度为 $O(2^n)$，空间复杂度为 $O(n)$。

子任务 2 中，使用普通布尔背包。块数和目标值都不超过 $O(n)$，两次判定的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

完整数据中，用位集合保存所有可达和。加入权值为 $w$ 的块时执行一次左移与按位或。设机器字长为 $W$，总时间复杂度为 $O(n^2/W)$，空间复杂度为 $O(n)$。

正确性证明

首先，最短闭合路线恰好对应于树上各节点子节点顺序的选择，因此每棵子树的叶子连续出现。

若算法回答 YES，总叶子数为偶数。第一次子集和给出一个包含 $c$、不包含 $d$ 的 $a$ 到 $b$ 半圈，第二次给出一个包含 $b$、不包含 $a$ 的 $c$ 到 $d$ 半圈。按两个集合的归属把普通根子树放入四个区间，并在四棵指定根子树内按照相应路径旁块的选择安排访问顺序，就能得到循环顺序 $a,c,b,d$。两个半圈都恰含 $L/2-1$ 个内部叶子，故两组要求同时成立。

若存在合法路线，则 $L$ 必为偶数，且四个指定叶子在环上交错。反转路线后可令顺序为 $a,c,b,d$。路线中 $a$ 到 $b$ 半圈选中的所有路径旁子树正好构成第一次子集和的一个解；同理，$c$ 到 $d$ 半圈给出第二次子集和的一个解。因此算法的两次判定都会成功。

综上，算法当且仅当存在合法最短路线时输出 YES。