230707 // 换根复习续

A. 叶子的染色

http://222.180.160.110:1024/contest/3824/problem/1

不难发现题目非常难以看懂。其实题目的意思是，\(1\sim n\) 一定是叶子节点（就不能明说吗）。那么问题来了，这是一棵无根树，那么我们所选取的根会对答案造成影响吗？

由于 \(c_u\) 给定的是根节点到 \(u\) 路径上最后一个颜色，我们假设现在需要将根从 \(x\) 变成相邻的 \(y\)，那么分讨一下：

1. \(x\) 已染色，\(y\) 已染色：

   1. \(x\) 与 \(y\) 同色：

      该种情况不可能出现，因为对于在以 \(x\) 为根的树中，将 \(y\) 变为无色仍能达到要求，不可能成为最优解。

   2. \(x\) 与 \(y\) 异色：

      因为 \(y\) 已染色，在 \(y\) 引导的子树中，从 \(x\) 到任意叶子节点路径上的最后一个已染色结点都不可能是 \(x\)，所以可以直接将 \(y\) 提为根，代价不变。

2. \(x\) 已染色，\(y\) 未染色：

   这说明了 \(y\) 引导的子树的叶子没有任何一个以 \(y\) 为最后颜色，有的可能以 \(x\) 为最后颜色。那么我们只需要将 \(x\) 变为无色，\(y\) 变为 \(x\) 原本的颜色即可，代价不变。

3. \(y\) 已染色，\(x\) 未染色：

   全树中没有任何一个叶子节点依赖于 \(x\)，直接将 \(y\) 提上来即可。代价不变。

所以我们得到结论，随便选一个点当根都只能得到相同的答案。

注意大部分题解在这里得到的结论是任选一个非叶子当根，但实际上由上述推导可知任选一个点做根都是可以的。

设 \(f_{x, 0/1}\) 表示将 \(x\) 染成白色 / 黑色的最小代价，则有：

那有人可能就要问了，没有不将 \(x\) 染色这个选项吗？

从转移式子里可以看出来，将 \(x\) 染色还有让代价变得更小的可能性，要是不染色就不存在这种可能性了。况且，\(x\) 如果真的不需要染色，那么会在它的父节点处进行计算，总能得到正确的答案。

那根节点没有父节点，怎么办呢？我们知道，既然根节点可以染色，那说明至少有一个叶子依赖于根节点，那么将根节点染色的代价不会比将这些叶子染色的代价更大。

然后是初始化，对于叶子，\(f_{x, c_x} \gets 1, f_{x, 1 - c_x} \gets \inf\) 即可，对于非叶子，\(f_{x, 0/1} = 1\)。

时间复杂度 \(\mathcal O(n)\)。

#define int long long
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxn = 2e5 + 5;
int a[maxn];
int f[maxn][2];
int n, m, x, y, w;
std::vector<int> g[maxn];
inline int min(int x, int y) {
	return x < y ? x : y;
}
inline int max(int x, int y) {
	return x > y ? x : y;
}
void DFS(int x, int fa) {
	for (auto i : g[x]) {
		if (i == fa)
			continue;
		DFS(i, x);
		f[x][0] += min(f[i][0] - 1, f[i][1]);
		f[x][1] += min(f[i][1] - 1, f[i][0]);
	}
	return;
}
inline void add(int x, int y) {
	g[x].push_back(y);
	return;
}
int main() {
	read(n), read(m);
	for (int i = 1; i <= m; ++i) {
		read(a[i]);
		f[i][a[i]] = 1;
		f[i][!a[i]] = inf;
	}
	for (int i = 1; i < n; ++i) {
		read(x), read(y);
		add(x, y), add(y, x);
	}
	for (int i = m + 1; i <= n; ++i)
		f[i][0] = f[i][1] = 1;
	DFS(n, -1);
	print(min(f[n][0], f[n][1]));
	return 0;
}
} // namespace XSC062
#undef int

听说这道题好像也是有换根做法的，但是我开摆。

B. 关键网线

http://222.180.160.110:1024/contest/3824/problem/2