D1T2

称编号 \(> n\) 的点为新点。 由条件 1 可以推出树 \(T\) 为结点 \(1 \sim n\) 在树 \(T'\) 上的 虚树。 由条件 2 可以推出 \(\forall 1 \le u < v \le n + m, \operatorname{lca}(u, v) \le v + k\ ......

显然地，这 $t$ 座城市一定由每个连通块出一座得来，换言之，新修建道路的两城市原来一定不连通。 进一步可以想到，若选择了 $u, v$ 两座城市且它们连通，则 $u \rightsquigarrow v$ 上的所有城市都应被选择。 更进一步地可以推出，若选择的城市同属一个点双，则该点双内的所有城市 ......

首先全奇全偶的情况是容易的，将 $\bmod4$ 意义下相同的合并即可保持原来的奇偶状态，当只有两个是直接合并即可，归纳即可说明全奇全偶一定合法。 但关键的问题在于奇偶状态可能互相影响，一个直观的想法是将奇合并为一个 $x$，偶合并为一个 $y$，如果 $x,y$ 的奇偶性相同，那么它们即可合并，即 ......