题目描述
难度分:$1600$
输入$n(2 \leq n \leq 10^5)$,表示一棵$n$个节点的无向树(节点编号从$1$开始)。
然后输入$n-1$条边,每条边输入$x$、$y$、$t$,表示有一条无向边连接$x$和$y$,其中$t=1$表示这条边是好的,$t=2$ 表示这条边是坏的。
你需要选择一些点。如果点$v$在你选的点中,那么从$v$到$1$这条路径上的所有坏边都会变成好边。
问:最少需要选多少个点,才能使所有坏边变成好边?
输出两行:第一行是选的点的个数,第二行是这些点的编号(可以按任意顺序输出点的编号)。
输入样例$1$
5
1 2 2
2 3 2
3 4 2
4 5 2
输出样例$1$
1
5
输入样例$2$
5
1 2 1
2 3 2
2 4 1
4 5 1
输出样例$2$
1
3
输入样例$3$
5
1 2 2
1 3 2
1 4 2
1 5 2
输出样例$3$
4
5 4 3 2
算法
树形DP
突破口就是思考每条坏边被哪个节点$v$给改成好边最为划算,答案也比较明显:每条坏边应该被位于它子树中,最深的那个坏边的较深端点给改成好边。要选来操作的节点$v$应该满足自己的深度就是以自己为根的子树中,坏边端点的最深深度。
因此我们先遍历一遍边集,用一个$O(n)$的布尔数组$st$把所有坏边的端点做上标记,再做一遍DFS
,预处理出每个节点的深度数组$depth$。有了它们两个,就可以进行树形DP
了。
状态定义
$dp[u]$表示以$u$为根的子树中,坏边的最深深度(深度从$1$开始)。
状态转移
如果$st[u]=true$,那么初始化$dp[u]=depth[u]$,否则$dp[u]=0$。然后遍历$u$的子节点$v$,状态转移方程为$dp[u]=max(dp[u], max_v dp[v])$。
最后遍历$i \in [1,n]$,看哪些节点满足$depth[i]=dp[i]$,它们都是需要操作的节点$v$。
复杂度分析
时间复杂度
对整棵树进行了两遍DFS
,时间复杂度为$O(n)$。
空间复杂度
标记数组$st$,深度数组$depth$,以及$dp$数组都是$O(n)$规模的。不算输入的树所占空间,额外空间复杂度为$O(n)$。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n;
int depth[N], dp[N];
bool st[N];
vector<int> graph[N];
void dfs1(int u, int fa, int dep) {
depth[u] = dep;
for(int v: graph[u]) {
if(v == fa) continue;
dfs1(v, u, dep + 1);
}
}
void dfs2(int u, int fa, int dep) {
if(st[u]) dp[u] = dep;
for(int v: graph[u]) {
if(v == fa) continue;
dfs2(v, u, dep + 1);
dp[u] = max(dp[u], dp[v]);
}
}
int main() {
scanf("%d", &n);
memset(dp, 0, sizeof dp);
memset(st, 0, sizeof st);
for(int i = 1; i <= n; i++) {
graph[i].clear();
}
for(int i = 1; i < n; i++) {
int x, y, t;
scanf("%d%d%d", &x, &y, &t);
if(t == 2) st[x] = st[y] = true;
graph[x].push_back(y);
graph[y].push_back(x);
}
dfs1(1, 0, 1);
dfs2(1, 0, 1);
vector<int> ans;
for(int i = 1; i <= n; i++) {
if(depth[i] == dp[i]) {
ans.push_back(i);
}
}
int sz = ans.size();
printf("%d\n", sz);
for(int x: ans) {
printf("%d ", x);
}
return 0;
}