Codeforces Round 928 (Div. 4) G. Vlad and Trouble at MIT 题解 树形dp

本文主要是介绍Codeforces Round 928 (Div. 4) G. Vlad and Trouble at MIT 题解 树形dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Vlad and Trouble at MIT

题目描述

弗拉迪斯拉夫有个儿子非常想去麻省理工学院。麻省理工学院（摩尔多瓦理工学院）的学生宿舍可以用一棵树来表示，树上有 $n$ 个顶点，每个顶点代表一个房间，房间里正好有一个学生。树是一个连通的无向图，有 $n$ 个顶点和 $n-1$ 条边。

今晚，有三种类型的学生：

• 想参加派对和玩音乐的学生（标记为 $\text{P}$ ）；
• 想睡觉和享受安静的学生（标记为 $\text{S}$ ）；
• 无所谓的学生（标记为 $\text{C}$ ）。

最初，所有的边缘都是薄墙，允许音乐通过，因此当参加派对的学生放音乐时，每个房间都能听到。但是，我们可以在任何边缘放置一些厚墙–厚墙不允许音乐通过。

学校希望安装一些厚墙，这样每个参加派对的学生都可以播放音乐，而睡觉的学生却听不到。
由于大学在冠名权诉讼中损失惨重，他们要求您找出他们需要使用的最少厚墙数量。

输入描述

第一行包含一个整数 $t$ ( $1\le t\le 1000$ ) - 测试用例数。

每个测试用例的第一行包含一个整数 $n$ ( $2\le n\le 10^5$ ) - 树中的顶点数。

每个测试用例的第二行包含 $n-1$ 个整数 $a_2,\dots ,a_n$ ( $1\le a_i<i$ ) - 这意味着树中的 $i$ 和 $a_i$ 之间有一条边。

每个测试用例的第三行包含一个长度为 $n$ 的字符串 $s$，由字符 $\text{P}$、$\text{S}$ 和 $\text{C}$ 组成，表示学生 $i$ 的类型为 $s_i$。

所有测试用例中 $n$ 的总和不超过 $10^5$ 。

输出描述

对于每个测试用例，输出一个整数–所需的最小厚壁数。

样例输入

3
3
1 1
CSP
4
1 2 2
PCSS
4
1 2 2
PPSS

样例输出

1
1
2

原题

CF——传送门

代码

#include <bits/stdc++.h>
using namespace std;
#define max_Heap(x) priority_queue<x, vector<x>, less<x>>
#define min_Heap(x) priority_queue<x, vector<x>, greater<x>>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
const double PI = acos(-1);#define INF 1e9 // 无穷大
const int maxn = 1e5 + 6;
int n;
string s;               // 节点类型
vector<int> edge[maxn]; // 存储从根节点指向子节点的有向边
int dp[maxn][3];        // dp[i][0]表示不接触水流，dp[i][1]表示只接触红色水流，dp[i][2]表示只接触蓝色水流void dfs(int u)
{dp[u][0] = INF; // 初始化为无穷大，便于dp求三种情况最小值if (s[u] != 'S')dp[u][1] = 0;elsedp[u][1] = INF; // 若该节点产生蓝色水流，则无法做到只接触红色水流if (s[u] != 'P')dp[u][2] = 0;elsedp[u][2] = INF; // 若该节点产生红色水流，则无法做到只接触蓝色水流int tot = 0;for (int v : edge[u]){// 深搜，dp从叶子节点往根节点转移dfs(v);dp[u][1] = dp[u][1] + min({dp[v][1], dp[v][2] + 1, dp[v][0]}); // 只接触红色水流所需墙壁和，三种情况，其中只有子节点为蓝色水流需要加一个墙壁dp[u][2] = dp[u][2] + min({dp[v][2], dp[v][1] + 1, dp[v][0]}); // 只接触蓝色水流所需墙壁和，三种情况，其中只有子节点为红色水流需要加一个墙壁tot += dp[v][0];                                               // 无水流经过所需墙壁和}if (s[u] != 'C') // 如果不为'C'，则该节点本身能产生水流，所以tot赋值无穷大，表示无法无水流tot = INF;dp[u][0] = min({tot, dp[u][1] + 1, dp[u][2] + 1}); // 该节点无水流的情况有三种：来者无水流，有水流+1个墙壁
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 本题策略：将'S'类比蓝色水流，将'P'类比红色水流，它们从叶子节点往根节点流，目的是设置最少墙壁使得蓝色水流和红色水流不交汇int t;cin >> t;while (t--){cin >> n;// 记得清空之前测试中的边for (int i = 1; i <= n; i++){edge[i].clear();}int v;for (int i = 2; i <= n; i++){cin >> v;edge[v].push_back(i);}cin >> s;// 补充无关元素，使下标从1开始一一对应节点s = '0' + s;dfs(1);// 取三者最小值int ans = INT_MAX;for (int i = 0; i < 3; i++){ans = min(ans, dp[1][i]);}cout << ans << '\n';}return 0;
}

这篇关于Codeforces Round 928 (Div. 4) G. Vlad and Trouble at MIT 题解 树形dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---