链接：https://codeforces.com/contest/1153/problem/D
思路：令dp[u]表示u的子树中传上来的数是第k大的数，那么如果边是min，dp[u] = sum{dp[v]}， 如果是max，dp[u] = min{dp[v]}, 最后k - dp[1] + 1就是答案。
代码：
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
|
using namespace std;
const int maxn = 3e5 + 5;
int f[maxn];
int ok[maxn];
int n, k;
vector<int> G[maxn];
int dp[maxn];
int deg[maxn];
void (int u, int fa){
if(ok[u] == 1 && deg[u]) dp[u] = 1e9;
for(auto &v : G[u]){
if(v == fa) continue;
dfs(v, u);
if(ok[u] == 0) dp[u] += dp[v];
else dp[u] = min(dp[u], dp[v]);
}
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> ok[i];
}
for (int i = 2; i <= n; ++i) {
cin >> f[i];
G[i].emplace_back(f[i]);
G[f[i]].emplace_back(i);
deg[f[i]]++;
}
for(int i = 1; i <= n; i++) if(!deg[i]) dp[i] = 1, k++;
dfs(1, 0);
cout << k - dp[1] + 1 << 'n';
return 0;
}
|
近期评论