Choosing Capital for Treeland

题面翻译

Treeland国有n个城市，这n个城市连成了一颗树，有n-1条道路连接了所有城市。每条道路只能单向通行。现在政府需要决定选择哪个城市为首都。假如城市i成为了首都，那么为了使首都能到达任意一个城市，不得不将一些道路翻转方向，记翻转道路的条数为k。你的任务是找到所有满足k最小的首都。

输入格式

输入包含多个测试点。对于每个测试点，每个测试点的第一行为一个正整数n（$2<=n<=2·10^{5}$）。接下来 n-1 行，每行两个正整数 $a_i$，$b_i$ ，表示城市a到城市b有一条单向通行的道路。输入以空格分隔，以EOF结尾。

输出格式

对于每个测试点，第一行输出k，第二行升序输出所有满足条件的首都的编号。

分析

发现自己写的时候根本没有发现有多组数据，实际上就根本没有多组数据。。。

我们发现，如果选定某一个点作为首都，可以 $O(n)$ 求出所对应的道路。

但实际上，一共有 $n$ 个点可以作为首都，如果逐个考虑， $O(n^2)$ 难以接受！

不妨考虑答案之间的联系。

如果记以 $u$ 为首都的答案为 res[v]。

对于相邻的两点 $u, v$ ，显而易见的是只有一条边是受到影响的， 即$\lparen u, v \rparen$：

  • 除去边 $\lparen u, v\rparen$，剩下的边可以分成两类。
  • 一类距离点 $u$ 更近的，一类是距离点 $v$ 更近的。
  • 无论首都是 $u$ 还是 $v$ 这些边对答案都没有影响。

那么就可以 $O(1)$ 地从一个点所对应的答案转移到另一个点。

像这样，一共转移 $n - 1$ 次，复杂度为 $O(n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

using pii = pair<int, int>;

int n, now, ans;

int st[N], top;

vector<pii> g[N];

void dfs_(int u, int fa){
    for (auto [v, ovO] : g[u]){
        if (v == fa) continue;
        now += 1 - ovO; dfs_(v, u);
    }
}

void dfs(int u, int fa, int now){
    if (now == ans) st[++top] = u;
    else if (now < ans) ans = now, top = 0, st[++top] = u;
    for (auto [v, ovO] : g[u]){
        if (v == fa) continue;
        if (ovO) dfs(v, u, now + 1);
        else dfs(v, u, now - 1);
    }
}

signed main(){
    
    cin >> n;
    
    for (int i = 1, u, v; i < n; i++){
        cin >> u >> v;
        g[u].push_back({v, 1}); // 尊度边
        g[v].push_back({u, 0}); // 假度边
    }
    
    dfs_(1, 0);
    dfs(1, 0, ans = now);
    
    cout << ans << endl;
    
    sort(st + 1, st + 1 + top);
    
    for (int i = 1; i <= top; i++)
        cout << st[i] << " ";
    
    return 0;
}

Written with StackEdit中文版.