题目描述

难度分:$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;
}