题意：给一个树形图(有向树)，n个节点，n-1条有向边，要求选一个节点作为根，使需要改变方向的边的数目最少。并输出所有可能作为根的点。

设dp[i]表示以i为根，需要改变多少个边方向

题解：首先dfs从下向上dp[i],然后在dfs一次从上更新dp[i]

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int head[maxn], tot, dp[maxn];
const int inf = 1e9;
int mm = inf;
struct Edge {
    int u, v, opt, next;
}edge[maxn];

void init() {
    memset(head, -1, sizeof(head)); tot = 1;
}
void add(int u, int v, int opt) {
    edge[++tot].u = u; edge[tot].v = v;
    edge[tot].opt = opt; edge[tot].next = head[u];
    head[u] = tot;
}

void dfs1(int u, int fa) {
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int to = edge[i].v;
        if (to == fa) continue;
        dfs1(to, u);
        dp[u] += dp[to] + (edge[i].opt == 0);
    }
}

void dfs2(int u, int fa) {
    mm = min(mm, dp[u]);
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int to = edge[i].v;
        if (to == fa) continue;
        if (edge[i].opt == 1) {
            dp[to] = dp[u] + 1;
        } else {
            dp[to] = dp[u] - 1;
        }
        dfs2(to, u);

    }
}

int main() {
    int n, u, v;
    scanf("%d", &n);
    init();
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d%d", &u, &v); 
        add(u, v, 1); add(v, u, 0);
    }
    dfs1(1, 0); 
//    for (int i = 1; i <= n; i++) cout << dp[i] << " "; cout << endl;
    dfs2(1, 0);
//    for (int i = 1; i <= n; i++) cout << dp[i] << " "; cout << endl;
    printf("%d\n",  mm);
    for (int i = 1; i <= n; i++) {
        if (dp[i] == mm) {
            printf("%d ", i);
        }
    }
    return 0;
}