CF 734E Anton and Tree

题目描述

http://codeforces.com/problemset/problem/734/E

Solution

每次操作相当于将同色连通块变色

所以我们首先按照将同色连通块缩点，然后我们得到一棵新树

这棵树上相邻点异色，需要的最少操作次数为 $\lceil\frac{d}{2}\rceil$，其中 $d$ 是这棵树的直径

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <iomanip>
#include <tuple>
#define maxn 200010
#define ll long long
using namespace std;

int n, m, a[maxn];

pair<int, int> E[maxn];

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

inline void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return ; 
    fa[fx] = fy;
}

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int f[maxn], ans;
void dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dfs(v, u); ans = max(ans, f[u] + f[v] + 1); 
        f[u] = max(f[u], f[v] + 1); 
    }
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; init_fa(n); 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        E[i] = { x, y }; if (a[x] == a[y]) merge(x, y); 
    }
    for (int i = 1; i < n; ++i) {
        int u, v; tie(u, v) = E[i];
        if ((u = find(u)) != (v = find(v))) add_edge(u, v), add_edge(v, u);
    } dfs(find(1), 0); cout << (ans + 1) / 2 << "\n"; 
    return 0;
}