백준 12746 - Traffic (Large)

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

12746번: Traffic (Large)

[알고리즘 분류]

LCA

Topological Sort

DP

 

 

 웰노운 비빔밥 문제다.

 

 먼저, 트리 위의 경로는 LCA를 이용하여 두 경로의 합으로 쪼갤 수 있다. 이 위에 값을 1씩 올려주는 과정은 imos법을 사용하면 된다. 아래에서 위로 올려주며 값을 더해줄 것이다. 이렇게 하기 위해서는 정점 \(u\)와 정점 \(v\)에 \(1\)을 더해주고, \(lca(u, v)\)에는 \(-2\)를 더해주면 된다.

 트리의 루트로 올라가는 간선으로 트리를 재구성하고, 누적 합을 구해주자. 간선 \(u\rightarrow par_u\)을 지나는 사람들의 수는, \(dp[u]\)에 들어있게 된다. 이들 중 최댓값에 해당하며, 사전 순으로 최소인 간선을 열심히 찾으면 된다.

 

 정답 코드는 다음과 같다.

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
 
//const ld eps = 1e-9;
const ll mod = 998244353;
const ll inf = 1e9;
 
#define all(v) (v).begin(),(v).end()
#define compress(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define X first
#define Y second
 
 
 
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define MAX(a, b) a = (((a)<(b))?(b):(a))
#define MIN(a, b) a = (((a)>(b))?(b):(a))
 
 
// end of def
 
 
ll dp[232323];
map<pii, int> dpp;
vector<int> g[232323];
vector<int> g2[232323];
vector<pii> edge;
int par[232323];
int ind[232323];
int dep[232323];
int sp[19][232323];
 
 
void dfs(int x, int b){
    par[x] = b;
    dep[x] = dep[b] + 1;
    for (int i: g[x]){
        if (i == b) continue;
        dfs(i, x);
    }
}
 
void init(int sz){
    for (int i=1;i<=sz;i++) sp[0][i] = par[i];
    for (int i=1;i<19;i++){
        for (int j=1;j<=sz;j++){
            sp[i][j] = sp[i-1][sp[i-1][j]];
        }
    }
    for (int i=1;i<=sz;i++){
        ind[par[i]]++;
        if (par[i]) g2[i].emplace_back(par[i]);
    }
}
 
int qry(int u, int v){
    if (dep[u] > dep[v]) swap(u, v);
    int go = dep[v] - dep[u];
    for (int i=18;i>=0;i--){
        if (go >= (1 << i)){
            go -= 1 << i;
            v = sp[i][v];
        }
    }
    if (u == v) return u;
 
    for (int i=18;i>=0;i--){
        if (sp[i][u] == sp[i][v]) continue;
        u = sp[i][u];
        v = sp[i][v];
    }
    return sp[0][v];
}
 
void add(int u, int v){
    edge.emplace_back(u,v);
    int p = qry(u, v);
    dp[u]++; dp[v]++; dp[p]-=2;
}
 
void ts(int sz){
    deque<int> dq;
    for (int i=1;i<=sz;i++) if (!ind[i]) {
        dq.emplace_back(i);
    }
    while (!dq.empty()){
        int x = dq.front();
        dq.pop_front();
        for (int i: g2[x]){
            int fi=i,se=x;
            if (fi>se) swap(fi,se);
            dp[i] += dp[x];
            dpp[{fi,se}] = dp[x];
            if (!(--ind[i])){
                dq.emplace_back(i);
            }
        }
    }
}
 
int main() {
    fastio;
    int n,m;cin>>n>>m;
    for (int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(1, 0);
    init(n);
    while (m--){
        int u,v;cin>>u>>v;
        add(u,v);
    }
    ts(n);
    //for (int i=1;i<=n;i++) cout<<dp[i]<<" "; cout<<endl;
    m = 0;
    for (auto [i,j]: dpp) MAX(m, j);
    vector<pii> cand;
    for (auto[i,j]:dpp)if (j == m) cand.emplace_back(i);
    sort(all(cand));
    pll ans = cand[0];
    cout << ans.X << " " << ans.Y << " " << m << endl;
 
    return 0;
}