[AGC004F] Namori 题解

这里给出一种与其他题解完全不同的实现方式。

思路

发现图要么是一棵树，要么是一颗基环树。

树

我们首先考虑树如何操作。

我们可以 \(\text{dfs}\) 这颗树。

对于每个点维护一个 \(w,h\)，表示这个点想要变成白色 \(w\) 次，想要变成黑色 \(h\) 次。

容易发现每个点最初状态都为 \(w=0,h=1\)。

我们一次往上合并。

对于一个点，我们合并都向它的父亲合并这个信息。

由于我们是从叶子节点往上推，所以一个点只会与他的父亲进行操作。

可以发现，若一个点想要变成黑色 \(h\) 次，那么必然要它的父亲变白 \(h\) 次。

同理，若一个点想要变成白色 \(w\) 次，那么必然要它的父亲变黑 \(w\) 次。

这样就可以往上转移。

再考虑消取一些情况。

一个点可以变黑的条件是它需要为白色。

一个点可以变白的条件是它需要为黑色。

那么这高速了我们，想要变黑色的数量可以与变白色的数量相互抵消。

抵消后，\(w,h\) 只有一个变量有值，我们把他统计到答案中去。

容易得知，无解的情况便是到达了根节点 \(w,h\) 还不为 \(0\)。

这就表示不能完全清空。

基环树

考虑从树的做法拓展到基环树。

我们将环上的一条边提取出来，就又变成了一条边和一棵树。

由于我们将这条边要么染白 \(k\) 次，要么染黑 \(k\) 次。

那么我们可以现将其染白一次看一看是什么情况。

对应到树上就是两个点 \(w=k-1,h=0\)，其中若是染黑则 \(k\) 为负数。

可以发现，我们若是改变两个点 \(w\) 的值，最终对应到答案上要么是两个值抵消，要么是一起加在了根上。

这又启示了我们，更改 \(k\) 要么是无解变为有解，要么从有解变为更优解。

1. 无解变为有解。

   我们可以将 \(k=0\)，与 \(k=1\) 进行对比，若是根 \(w,h\) 变了，那么我们只需要将 \(k\) 赋为一个可以将其消为 \(0\) 的值即可。

2. 有解变为更优解

   很容易猜测到，\(k\) 的取值与答案会构成一个单峰函数，那么我们直接三分解决即可。

从上文可以看出，这个做法的思维含量较低，主要是通过观察答案性质解决。

无需从环的长度以及大量的数学去推导。

缺点可能是由于需要 \(\text{dfs}\) 很多次，可能常数较大。

Code

AC记录。