CF219D Choosing Capital for Treeland 题解

题目链接：CF219D Choosing Capital for Treeland

题意：Treeland国有n个城市，这n个城市连成了一颗树，有n-1条道路连接了所有城市。每条道路只能单向通行。现在政府需要决定选择哪个城市为首都。假如城市i成为了首都，那么为了使首都能到达任意一个城市，不得不将一些道路翻转方向，记翻转道路的条数为k。你的任务是找到所有满足k最小的首都。

随便找一个点 $rt$ 跑一遍dfs，求出这个 $dp[rt]$ 的值

然后 $dp[u] \to dp[v]$ 的转移显然与 $(u,v)$ 有关

判断一下然后转移一下就没了

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)
struct Edge
{
    int u,v,next;
}e[N<<1];
int n,dp[N];
int pos=1,head[N],r[N<<1];
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
int dfs1(int u,int f)
{
    int res=0;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==f)continue;
        if(!r[i])++res;
        res+=dfs1(v,u);
    }
    return res;
}
void dfs2(int u,int f)
{
    dp[u]+=dp[f];
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==f)continue;
        if(r[i])++dp[v];
        else --dp[v];
        dfs2(v,u);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,u,v; i<n; i++)
    {
        cin >> u >> v;
        addEdge(u,v);r[pos]=1;
        addEdge(v,u);
    }
    dp[1]=dfs1(1,0);int mn=INF;
    dfs2(1,0);
    for(int i=1; i<=n; i++)
        mn=min(mn,dp[i]);
    cout << mn << endl;
    for(int i=1; i<=n; i++)
        if(dp[i]==mn)cout << i << " ";
    return 0;
}

---

题外话：

真的离了谱了，我换电脑之前写的这篇文章没发博客上

然后今天20220606花了2小时用爬虫和自己写的比对程序搞了半天才发现（恼

upd.20240503 至少现在不用担心了。