D. Choosing Capital for Treeland
题意
给出一颗有方向的n个节点的树，现在要选择一个点作为首都。
问最少需要翻转多少条边，使得首都可以到所有其他的城市去，以及相应的首都可以是哪些点。
思路
先忽略掉树中的方向，dp[i]表示i节点到它的子树所有点最少需要翻转的边。
进行第一遍dfs
如果u-v的方向是u-->v，那么dp[u]=dp[u]+dp[v];，否则dp[u]=dp[u]+dp[v]+1;，表示u-v这条边要翻转。
这时根节点的dp值就是根节点作为首都需要翻转的边，进行第二遍dfs：
dp[i]表示i作为首都需要翻转的最少边的数量
如果u-v的方向是u-->v，那么dp[v]=dp[u]+1;，否则dp[v]=dp[u]-1。
代码
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
vector<int>vec[N],ans;
int n,dp[N];
map<int,map<int,int> >mp;
void dfs(int u,int fa)
{
for(int v:vec[u])
{
if(v==fa) continue;
dfs(v,u);
dp[u]+=(dp[v]+!mp[u][v]);
}
}
void dfs2(int u,int fa)
{
for(int v:vec[u])
{
if(v==fa) continue;
if(mp[u][v]) dp[v]=dp[u]+1;
else dp[v]=dp[u]-1;
dfs2(v,u);
}
}
int main()
{
scanf("%d",&n);
for(int i=1; i<n; i++)
{
int u,v;
scanf("%d%d",&u,&v);
mp[u][v]=1;//mp[u][v]==1,表示u-v的方向是u-->v
vec[u].pb(v);
vec[v].pb(u);
}
dfs(1,0);
dfs2(1,0);
int maxn=inf;
for(int i=1; i<=n; i++)
{
if(dp[i]<maxn)
{
maxn=dp[i];
ans.clear();
ans.pb(i);
}
else if(dp[i]==maxn)
ans.pb(i);
}
printf("%d
",maxn);
for(int v:ans)
printf("%d ",v);
printf("
");
return 0;
}