백준 12746번 - Traffic (Large)

https://www.acmicpc.net/problem/12746

12746번: Traffic (Large)

 

• 필요한 배경지식

최소 공통 조상(LCA), 트리에서의 다이나믹 프로그래밍

 

 

 

• 문제 해결 방법

이전에 포스팅한 농장 관리 문제에서 풀이한 방법과 같은 방법을 이용하여 철로를 지난 사람의 수를 구할 수 있습니다.

 

농장 관리 문제와 다른점은 업데이트가 모두 이루어진 후 결과값을 출력하기 때문에, 노드에 추가되는 가중치를 배열에 누적하여 저장하고 DP로 문제를 해결할 수 있습니다.

 

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
#define MAX 222222
using namespace std;

int N, M;
int ac[MAX+1][21]{};
int dpt[MAX+1]{};
vector<int> adj[MAX+1]{};
int cnt[MAX+1]{};

void dfs(int now, int parent) {
    dpt[now] = dpt[parent] + 1;
    ac[now][0] = parent;

    for (int i = 1; i <= 20LL; i++)
        ac[now][i] = ac[ac[now][i-1]][i-1];

    for (auto next : adj[now]) {
        if (next == parent) continue;
        dfs(next, now);
    }
}

int lca(int x, int y) {
    if (dpt[x] > dpt[y]) swap(x, y);
    for (int i = 20LL; i >= 0; i--) { 
        if (dpt[y] - dpt[x] >= (1 << i)) 
            y = ac[y][i];
    }
    if (x == y)return x;
    for (int i = 20LL; i >= 0; i--) {
        if (ac[x][i] != ac[y][i]) {
            x = ac[x][i];
            y = ac[y][i];
        }
    }
    return ac[x][0];
}

void dfs2(int now, int par){
	for(auto &i : adj[now]){
		if(i != par) dfs2(i, now), cnt[now] += cnt[i];
	}
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    int a,b;
    for(int i=1; i<N; i++){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, 0);

    while(M--){
        cin>>a>>b;
        int l = lca(a,b);
        cnt[a]++;
        cnt[b]++;
        cnt[l]-=2;
    }

    dfs2(1, 0);
    int ans = 0;
    a=0, b=1;
	for(int i=2; i<=N; i++){
        if(ans < cnt[i]){
            ans = cnt[i];
            a = ac[i][0];
            b = i;
        } else if(ans == cnt[i]){
            int j = ac[i][0];
            if(i<a || j<a) a = i, b = j;
        } else continue;
        if(a>b) swap(a,b);
    }
    cout<<a<<' '<<b<<' '<<ans;
}