Codeforces Round

传送门：https://codeforces.ml/contest/1263/problem/F

题意

给两棵树，一颗在上面，另一颗在下面，两棵树的叶子节点都连接着一台机器。

问，最多删掉多少条边，每个机器都至少存在一条路径到达两个根节点1中的一个。

思路

考虑dp，设dp[i]表示前i个机器通电的最大删除边数。 设val[0/1][L][R]表示上/下树中区间[L,R]最大删除边数。 即转移方程为： $$dp[i]=max(dp[i],dp[j]+max(val[0][j+1][i],val[1][j+1][i]))$$

所以要怎么处理这个val呢？

在树上处理，第一想到的就是dfs！

因为叶子节点都是与机器相连的，所以n个叶子节点类似于线段的端点。 对于每个子树，都会有一个端点区间，当删除该子树时，该区间内的机器无法到达根节点。 删除该子树后，贡献为子树大小即size[i]条边。

dfs过程中不断更新val[L][R]即可。

Code

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
##include "bits/stdc++.h"
using namespace std;

##define endl "\n"
##define eb emplace_back
##define mem(a, b) memset(a , b , sizeof(a))

const int N = 2e3 + 10;
int val[2][N][N];
int l[2][N], r[2][N];
vector<int> g[2][N];
int siz[N];
int dp[N];

void dfs(int u, int fa, int opt) {
    if(u != 1) siz[u] = 1;
    for(auto v : g[opt][u]) {
        if(v == fa) continue;
        dfs(v, u, opt);
        siz[u] += siz[v];
        l[opt][u] = min(l[opt][u], l[opt][v]);
        r[opt][u] = max(r[opt][u], r[opt][v]);
    }
    val[opt][l[opt][u]][r[opt][u]] = max(val[opt][l[opt][u]][r[opt][u]], siz[u]);
}

void solve() {
    int n; cin >> n;
    mem(l, INF);
    for(int i = 0;i < 2; i++) {
        siz[1] = 0;
        int a; cin >> a;
        for(int j = 2;j <= a; j++) {
            int u; cin >> u;
            g[i][u].eb(j);
            g[i][j].eb(u);
        }
        for(int j = 1;j <= n; j++) {
            int v; cin >> v;
            l[i][v] = j;
            r[i][v] = j;
        }
        dfs(1, 0, i);
    }
    for(int i = 1;i <= n; i++) {
        for(int j = 0;j < i; j++) {
            dp[i] = max(dp[i], dp[j] + max(val[0][j + 1][i], val[1][j + 1][i]));
        }
    }
    cout << dp[n] << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/12/codeforces-round-603-div-2-f/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！