Looking for the "Best Roots" in a directional tree diagram?

(This comes from a recently completed programming contest)

You are given G, a connected graph with N nodes and edges N-1.

(Note that this means that G forms a tree.)

Each edge G is directed. (not necessarily up to any root)

For each vertex v of G, we can invert zero or more edges so that there is a directed path from every other vertex w to v. Let the minimum possible number of edge inversions for this be f (v).

By what linear or logarithmic algorithm can we determine the subset of vertices having the minimum common f (v) (including the value f (v) of these vertices)?

For example, consider 4 vertex graphs with these edges:

A<--B
C<--B
D<--B

The value f (A) = 2, f (B) = 3, f (C) = 2 and f (D) = 2 ...

.. {A, C, D} 2

(, f (v), f (v) - )

:

:

int main()
{
    struct Edge
    {
        bool fwd;
        int dest;
    };

    int n;
    cin >> n;

    vector<vector<Edge>> V(n+1);

    rep(i, n-1)
    {
        int src, dest;
        scanf("%d %d", &src, &dest);

        V[src].push_back(Edge{true, dest});
        V[dest].push_back(Edge{false, src});
    }

    vector<int> F(n+1, -1);

    vector<bool> done(n+1, false);

    vector<int> todo;
    todo.push_back(1);
    done[1] = true;
    F[1] = 0;

    while (!todo.empty())
    {
        int next = todo.back();
        todo.pop_back();

        for (Edge e : V[next])
        {
            if (done[e.dest])
                continue;

            if (!e.fwd)
                F[1]++;
            done[e.dest] = true;
            todo.push_back(e.dest);
        }
    }

    todo.push_back(1);

    while (!todo.empty())
    {
        int next = todo.back();
        todo.pop_back();

        for (Edge e : V[next])
        {
            if (F[e.dest] != -1)
                continue;

            if (e.fwd)
                F[e.dest] = F[next] + 1;
            else
                F[e.dest] = F[next] - 1;

            todo.push_back(e.dest);
        }
    }

    int minf = INT_MAX;

    rep(i,1,n)
        chmin(minf, F[i]);

    cout << minf << endl;

    rep(i,1,n)
        if (F[i] == minf)
            cout << i << " ";
    cout << endl;

}