自动搬运

查看原文

来自洛谷，原作者为

	HFanGDoDM 热夏你归来听蝉，再游于北方知寒。沿途不枉为少年，终有个结局圆满。

搬运于2025-08-24 22:51:11，当前版本为作者最后更新于2023-10-07 18:54:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意简述

给定一棵含有 $n$ 个结点的树。设有两人 A 和 B，初始位置分别为 $u$ 和 $v$ $(u\not=v)$。每一轮中，顺次执行以下两个操作：

• B 选择 一个与 B 当前结点直接相邻的结点，或 B 当前所处的结点。设该结点为 $x$，则 B 会前往结点 $x$。

• A 选择 一个与 A 当前结点直接相邻的结点，或 A 当前所处的结点。设该结点为 $x$，则 A 会前往结点 $x$。

过程中，A 和 B 互相清楚 自己和对方的位置。若某一个操作结束后，A 和 B 位于同一个结点，则 B 被 A 捉住。A 希望 在有限步数内 捉住 B，B 希望 A 不能在有限步数内 捉住 B。A 和 B 都足够聪明。

现可以对该树增加一些边。试求出 最少的加边 数量，使得对于所有 $(u,v)$，A 和 B 按照最优策略操作的情况下，A 不能在有限步数内 捉住 B。若不存在这样的加边方案，输出 $-1$。

数据范围

有多组测试数据。测试数据组数 $T$ 满足 $1\leqslant T\leqslant 10^4$。对于每组测试数据，$2\leqslant n\leqslant 10^5,1\leqslant u_i,v_i\leqslant n$。对于所有测试数据，$\sum n\leqslant 2\times10^5$，保证输入是一棵树。

解题思路

做法

若树是 菊花图，则无解。否则：

设树上 度数为 $1$ 的点的数量为 $a$（这里点 $u$ 的度数定义为与点 $u$ 直接相邻的点的数量），与点 $u$ 直接相邻 的所有点中度数为 $1$ 的点的数量为 $num_u$，则答案为

$$ans=\max(\lceil \dfrac{a}{2}\rceil,\displaystyle\max_{i=1}^nnum_i) $$

正确性证明

考虑加边后形成的图。由于 $\forall (u,v)$，都有 A 不能在有限步数内捉住 B，且 B 先行动，因此 $\forall (u,v)$，B 必然会 趋向于 一个位置 $p$，使得 A 所处的位置与 $p$ 之间存在 至少两条不完全重合的简单路径 $\implies$ 此时 A 与 B 所处的位置的一条简单路径上的一部分 必然属于一个简单环。

我们设一部分属于的 极大简单环 为 $C$。若 $|C|=3$，则 A 会从连接该环上某个点的路径上的一个点向该环逼近。

此时环 $C$ 上的 $3$ 个点向外连出的点集与边集会有以下几种情况：

• $3$ 个点中有向外的边的，只向外连出一条简单路径。此时 B 可以选择向环外走，但此后 A 不断逼近，由于 A 与 B 之间的路径数量变为 $1$ 条，因此最终 B 必然被堵在“死角”而被 A 抓住，只是延长了被抓住的时间而已。

• $3$ 个点中有向外的边的，属于另一个三元环，则另一个三元环的另两个点必然 不属于 环 $C$（否则环 $C$ 不是极大环），或产生路径与三元环的复合结构或三元环套三元环（均满足两两三元环之间只有一个点重合）的结构。当 B 行动至无三元环或路径可继续远离 A 时，A 不断深入 三元环与路径的复合结构。对于路径的情况，上文已经证明 B 一定会被 A 抓住。对于三元环的情况，形似多叉树，A 一定可以通过选择一个结点，满足该结点为几个三元环的 交汇点，锁定 B 的位置并堵住 B。若 B 尝试在一个 A 位于一个点的三元环上移动，尝试转移到其他三元环，则 A 一定能够 在这一步之内抓住 B。

注意，以下情况是不符合上述条件的：

• $3$ 个点中有向外的边，通向一个环 $C'$，满足 $|C'|\gt3$。则 B 不可能趋向 环 $C$，B 必然趋向环 $C'$，使得自己尽可能不被 A 抓住。

综上，若 B 趋向的环的大小为 $3$，则必然被 A 捉住。

若这个环的大小 $|C|\geqslant4$，则一旦 B 进入这个环，由于 B 和 A 每次只能移动一步，因此 B 不可能被 A 捉住。若 A 在该环内走一步，B 也顺这一方向走一步；若 A 不动，B 也不动。

我们得证：符合题意的图中，$\forall(u,v)$，B 总能成功到达一个环 $C$ 中，其中 $|C|\geqslant4$。

对于原树上的一对度数为 $1$ 的点 $x$ 和 $y$，若有其一 不属于 一个环 $C$ 满足 $|C|\geqslant4$，设 $x$ 到 $y$ 的路径为 $path(x,y)=(x,p_1,p_2,\dots,y)$，不妨设 $x$ 不属于一个这样的环 $C$，则令 $u=p_1,v=x$，此时若 B 行动一步只能走到 $u$，被 A 抓住；否则，B 不动，则 A 行动一步到达 $v$，抓住 B。$x$ 或 $y$ 有属于三元环的情况，上述已经证明。因此 B 一定被抓住，不合题意。

得证：$\forall$原树上的一对度数为 $1$ 的点 $(x,y)$，都有 $x,y\in C,|C|\geqslant4$。即：$\forall$ 原树上度数为 $1$ 的结点 $x$，都有 $x\in C,|C|\geqslant4$。

对于菊花图，由于其 直径（点数） $\leqslant3$，因此无论如何对度数为 $1$ 的点加边，都无法使得这些点属于一个环 $C$，$|C|\geqslant4$。若不是菊花图，则其直径 $\geqslant4$，因此总有加边方案。所以 菊花图无解，其他树有解。

根据上述推理，存在这样一种符合题意的方案：$\exists x,y$，路径 $(x,y)$ 上的点数 $\geqslant3$，点 $x,y$ 各属于一个环 $C,|C|\geqslant4$，该路径上的其他点不属于任何一个环。但是，我们可以发现，该方案恰好加了 $2$ 条边。我们总能 将这 $2$ 条边 $(u_1,v_1),(u_2,v_2)$ 断开，并连边 $(u_1,u_2),(v_1,v_2)$，此时路径 $(x,y)$ 及原环上的所有点都能属于一个环 $C,|C|\geqslant4$。此时仍然只连接了 $2$ 条边，是不劣的。

因此得证：必然存在一种最优方案，使得每个点都属于至少一个环 $C,|C|\geqslant4$。

首先我们需要满足每个点至少属于一个 简单环。这是一个经典问题，将度数为 $1$ 的点 两两配对，因此需要增加至少 $\lceil \dfrac{a}{2}\rceil$ 条边。然后，对于每一个点，与其直接相邻的所有度数为 $1$ 的点之间 不能直接连边（否则将形成三元环），每一个这样的点都需要与其他的 到这个点距离 $\geqslant2$ 的点进行配对。因此，对于点 $u$，我们至少需要增加 $num_u$ 条边。

得证：至少需要的边数为 $\max(\lceil \dfrac{a}{2}\rceil,\displaystyle\max_{i=1}^nnum_i)$。

具体实现

读入每一条边 $(u,v)$，增加点 $u$ 和 $v$ 的度数，并将每条边存下来。再扫每条边 $(u,v)$，统计 $num_u$ 和 $num_v$。若 $u$ 的度数为 $1$，则将 $num_v$ 加 $1$，反之亦然。

判断是否有结点的度数为 $n-1$，若存在，则原图为菊花图，输出 $-1$。否则，扫一遍 $num$，并将其中最大值与 $\lceil \dfrac{a}{2}\rceil$ 取最大值，即为答案。

时间复杂度分析

求度数、统计 $num$、判断是否无解、统计答案，每一步的复杂度均为 $O(n)$。

总时间复杂度 $O(\sum n)$，可以通过本题。

参考核心代码

for(i=1;i<n;i++){
    int u=R(),v=R();
    deg[u]++,deg[v]++;//统计度数
    edge.push_back({u,v});
}
for(i=0;i<n-1;i++){//计算每个点相邻的点中度数为1的点数
    if(deg[edge[i].first]==1)
        num1[edge[i].second]++;
    if(deg[edge[i].second]==1)
        num1[edge[i].first]++;
}
for(i=1;i<=n;i++)
    if(deg[i]==n-1){
        puts("-1");//菊花图则无解
        return;
    }
int num=0;
for(i=1;i<=n;i++)
    if(deg[i]==1)
        num++;
int ans=(num+1)>>1;//即为上述的a/2上取整
for(i=1;i<=n;i++)
    ans=max(ans,num1[i]);//求出答案
printf("%d\n",ans);