『缩点·树的直径』CF734E Anton and Tree

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

给一棵$n(n\le 200000)$个节点的树，每个点为黑色或白色。

一次操作可以使一个相同颜色的连通块变成另一种颜色。

求使整棵树变成一种颜色的最少操作数。

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

使用并查集缩点，使得任意相邻的两点颜色都不一样。

可以证明，从树的直径的终点开始染色一定是最优的。

其中 $L_3$ 是直径上的最后一段，显然有$L_{1,2}\le L_3$

且分叉出去的节点颜色是相同的，那么这意味着在完成$L_3$染色之前，$L_1/L_2$的染色一定会被染色完成。

观察规律，我们发现答案一定是：$$?(\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{l}\mathrm{e}\mathrm{n}+1)/2?$$

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <bits/stdc++.h>using namespace std;
const int N = 5e5;int n, res;
int f[N], fa[N], x[N], y[N], col[N];
vector < int > a[N];long long read(void)
{
    int s = 0, w = 0; char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}void Dfs(int x, int fa)
{
    f[x] = 0;for (int i=0;i<a[x].size();++i){
    int y = a[x][i];if (y == fa) continue;Dfs(y, x);res = max(res, f[x] + f[y] + 1);f[x] = max(f[x], f[y] + 1);}return;
}int get(int x) {
    if (fa[x] == x) return x;return fa[x] = get(fa[x]);
}int main(void)
{
    n = read();for (int i=1;i<=n;++i) {
    col[i] = read();fa[i] = i;}for (int i=1;i<n;++i) {
    x[i] = read(), y[i] = read();if (col[x[i]] == col[y[i]]) fa[get(x[i])] = get(y[i]); } for (int i=1;i<n;++i) {
    x[i] = get(x[i]);y[i] = get(y[i]);if (x[i] == y[i]) continue;a[x[i]].push_back(y[i]);a[y[i]].push_back(x[i]);}Dfs(get(1), 0);cout << (res + 1 >> 1);return 0;
}