codeforces 219D D. Choosing Capital for Treeland(트리 dp)

제목 연결:

codeforces 219D

제목 대의:

나무 한 그루를 주지만 그 가장자리는 방향이 있다. 한 도시를 선택하고 최소한 몇 변의 방향을 조정하면 한 도시가 모든 점에 도달할 수 있고 가장 작은 조정의 변수와 대응하는 점을 출력할 수 있느냐고 묻는다.

제목 분석:

dp[u]를 뿌리로 하는 자수에서 뿌리가 모두 도달할 수 있도록 하려면 방향의 가장자리를 바꾸어야 한다.

dir[v]기록점 v가 아버지 노드의 가장자리까지의 방향을 정의한다.

그리고 각 점을 뿌리로 끌어올리는 작업입니다.

dp[u]를 새로운 정의로 바꾸어 u를 뿌리로 나무 전체에 도달할 때 조정해야 할 변의 줄수를 설정합니다.

dp[u] = dp[p] + dir[u]?1:-1

자세한 내용은 코드를 보십시오. 이 문제는 D문제에서 상당히 물처럼 계산됩니다.

AC 코드:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX 200007

using namespace std;

int n,s,t;
vector<int> e[MAX];
vector<int> f[MAX];
int dp[MAX],dir[MAX];

void add ( int u , int v )
{
    e[u].push_back ( v );
    f[u].push_back ( 0 );
    e[v].push_back ( u );
    f[v].push_back ( 1 );
}

void dfs ( int u , int p )
{
    dp[u] = 0;
    for ( int i = 0 ; i < e[u].size() ; i++ )
    {
        int v = e[u][i];
        if ( v == p ) continue;
        dir[v] = f[u][i];
        dfs ( v , u );
        dp[u] += dp[v] + dir[v];
    }
}

void solve ( int u , int p )
{
    for ( int i = 0 ; i < e[u].size() ; i++ )
    {
        int v = e[u][i];
        if ( v == p ) continue;
        dp[v] = dp[u] + (dir[v]?-1:1);
        solve ( v , u );
    }
}


int main ( )
{
    while ( ~scanf ( "%d" , &n ))
    {
        for ( int i = 0 ; i < MAX ; i++ )
        {
            e[i].clear();
            f[i].clear();
        }
        for ( int i = 1 ; i < n ; i++ )
        {
            scanf ( "%d%d" , &s , &t );
            add ( s , t );
        }
        dfs ( 1 , -1 );
        solve ( 1 , -1 );
        int ans = 1<<29;
        for ( int i = 1 ; i <= n ; i++ )
            ans = min ( ans , dp[i] );
        printf ( "%d
" , ans );
        vector<int> pp;
        for ( int i = 1 ; i <= n ; i++ )
            if ( dp[i] == ans )
                pp.push_back ( i );
        sort ( pp.begin() , pp.end());
        for ( int i = 0 ; i < pp.size(); i++ )
            printf ( "%d " , pp[i] );
        puts ("");
    }
}