【换根DP】AcWing 4381. 翻转树边
2022-03-31 19:45:00 # ACM

题链

https://www.acwing.com/problem/content/description/4384/

题解

  1. 考虑换根 DP;
  2. u 向 v 连有向边则 dis(v, u) 记为 1，dis(u, v) = 0;
  3. 考虑以 1 为根节点
  4. 设 g[u] 表示以 u 为根节点的子树 从 u 到子树下所有点所需代价:
    • g[u] = g[vi] + dis(u, v);
  5. 设 f[u] 表示以 u 为中心的答案:
    • f[1] = g[1];
    • f[v] = g[v] + ( f[u] - (g[v] + dis(u, v)) ) + dis(v, u);
    • 化简可得 f[v] = f[u] - dis(u, v) + dis(v, u);
    • 对于 等式 右边的三部分
      • g[v] : 就是以 v 的子树的贡献
      • f[u] - (g[v] + dis(u, v)) : 就是除了 ( v 的子树和 (u, v) 这条边 ) 的贡献
      • dis(v, u) : 就是最后一部分 (v, u) 这条边的贡献
  6. 于是第一次 dfs 求 g[]，第二次求 f[]

代码

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
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
#define MS 200009

int n;
struct node{
    int poi, cost;
};
vector<node > vc[MS];
int ans[MS];

void dfs1(int u, int f){
    for(auto nb:vc[u]){
        auto v = nb.poi;
        if(v == f) continue;
        auto c = nb.cost;
        dfs1(v, u);
        ans[u] += ans[v] + c;
    }
}

void dfs2(int u, int f){
    for(auto nb:vc[u]){
        auto v = nb.poi;
        if(v == f) continue;
        auto c = nb.cost;
        ans[v] = ans[u] - c + (c^1);
        dfs2(v, u);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i=2;i<=n;i++){
        int u, v; cin >> u >> v;
        vc[u].push_back({v, 0});
        vc[v].push_back({u, 1});
    }
    dfs1(1, 0);
    // for(int i=1;i<=n;i++){
    //     cout << "ans[" << i << "] = " << ans[i] << "\n";
    // }
    dfs2(1, 0);
    int minn = n;
    for(int i=1;i<=n;i++){
        minn = min(minn, ans[i]);
    }
    cout << minn << "\n";
    // for(int i=1;i<=n;i++){
    //     cout << "ans[" << i << "] = " << ans[i] << "\n";
    // }
    for(int i=1;i<=n;i++){
        if(ans[i] == minn) cout << i << " ";
    }
    cout << "\n";
    
    return 0;
}
Prev
2022-03-31 19:45:00 # ACM
Next