https://codeforces.com/problemset/problem/219/D
【题意】
n个点m条边，找点，使得到全图的点的逆转道路数最小
【思路】
树形dp
建图时方向权值话（类似的在网络流中有所涉及），正向为0，逆向为1
转化为哪些节点在遍历全图后的价值最小
考虑每一个节点，子树可收获价值，从父亲也可以收获
2次dfs
第一次：子树更新父节点，得到dp[i]表示以i为子树的价值和（这里完成后可以的到的一个特殊的是根节点，此时的dp值已经表示为遍历全图的值了）
第二次：从父节点更新子节点，对于节点i，父亲j的节点的全图遍历答案已经得到（自上而下），那么通过父节点的答案就可以得到节点i的答案呢
【代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
struct node{int y,z;
};
vector<node>v[maxn];
int dp[maxn], dir[maxn];void dfs1(int x, int f) {dp[x] = 0;for (auto p : v[x]) {int y = p.y;int z = p.z;if (y == f)continue;dfs1(y, x);dp[x] += dp[y] + z;}
}void dfs2(int x, int f) {for (auto p : v[x]) {int y = p.y;int z = p.z;if (y == f)continue;dp[y] = dp[x] + (z ? -1 : 1);dfs2(y, x);}
}int main() {int n;while (~scanf("%d", &n)) {for (int i = 1; i <= n; i++)v[i].clear();memset(dp, 0, sizeof(dp));for (int i = 1; i < n; i++) {int x, y;scanf("%d%d", &x, &y);v[x].push_back({ y,0 });v[y].push_back({ x,1 });}dfs1(1, -1); dfs2(1, -1);int ans = 0x3f3f3f3f;for (int i = 1; i <= n; i++) {ans = min(ans, dp[i]);}printf("%d\n", ans);for (int i = 1; i <= n; i++) {if (ans == dp[i]) {printf("%d ", i);}}puts("");}
}