P9725 Chase Game 2 题解

· · 题解

题意简述

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

过程中，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 个点向外连出的点集与边集会有以下几种情况：

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

综上，若 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);