[백준 7045] Tree Cutting

[ghdcksgml1]

ㅋㅋㅋ 스토리가 이어져서 문제는 재밌네요. (난이도는 재미없음)

After Farmer John realized that Bessie had installed a "tree-shaped" network among his N (1 <= N <= 10,000) barns at an incredible cost, he sued Bessie to mitigate his losses.

농부 존은 베시가 그의 N개의 엄청난 비용으로 외양간들 사이에 트리모양으로 네트워크 설치를 한걸 알고나서 그는 그의 손실을 메꾸기 위해서 베시에게 소송을 제기했다.

Bessie, feeling vindictive, decided to sabotage Farmer John's network by cutting power to one of the barns (thereby disrupting all the connections involving that barn).

복수심에 가득찬 베시는 외양간들 중 하나의 네트워크를 자르기로 결정했다. ( 그렇게 함으로써 외양간에 관련된 모든 연결들은 방해받는다.)

When Bessie does this, it breaks the network into smaller pieces, each of which retains full connectivity within itself.

베시가 이것을 하면, 네트워크를 더 작은 조각으로 나눠지게 되고, 각각의 조각들은 그 자체로 연결을 유지한다.

In order to be as disruptive as possible, Bessie wants to make sure that each of these pieces connects together no more than half the barns on FJ. 

가능한  한 방해하기 위해서 베시는 농부존의 외양간의 반절이 넘지 않게 네트워크를 각각의 조각으로 나누려고 한다.

Please help Bessie determine all of the barns that would be suitable to disconnect.

베시를 도와 연결을 끊기위해 적합한 외양간들을 결정해주자.

---

트리에서의 다이나믹프로그래밍을 해주시면 됩니다. (USACO 문제는 기본적으로 난이도가 1,2단계정도 낮게 책정되는듯..)

// 언어 : C++ , (성공/실패) : 1/2 , 메모리 : 2024 KB , 시간 : 4ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h> // memset

using namespace std;

vector<int> adj[10001];
int MAX[10001];
int SUM[10001];
bool visit[10001];

void dfs(int x){
    visit[x] = true;
    SUM[x] = 1;
    for(int i=0;i<adj[x].size();i++){
        if(visit[adj[x][i]]) continue;
        dfs(adj[x][i]);
        MAX[x] = max(MAX[x],SUM[adj[x][i]]);
        SUM[x] += SUM[adj[x][i]];
    }
}

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N; cin>>N;
    for(int i=0;i<N-1;i++){
        int x,y; cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1);
    bool trigger = false;
    for(int i=1;i<=N;i++){
        if(max(MAX[i],N-SUM[i]) <= N/2){
            trigger = true;
            cout<<i<<'\n';
        }
    }
    if(!trigger) cout<<"NONE";

    return 0;
}

---

sue: 고소하다

mitigate: 완화시키다

vindictive: 앙심을 품은

sabotage: 방해하다, 파괴하다

power to: 총력을 기울이다.

thereby: 그렇게 함으로써

retain: 유지하다