백준17518 Wind of Change

작성일 | In

문제 링크

  • http://icpc.me/17518

사용 알고리즘

  • Centroid Decomposition

시간복잡도

  • $O(N \log^2 N)$

풀이

루비 5 문제를 푸는 사람이라면 모두가 알고 있을 사실 2가지를 짚고 넘어가겠습니다.

  • 트리 $T$의 정점 $i$에서 $j$로 가는 경로의 거리 $D(i, j)$는 $T$의 Centroid Tree $C_T$에서 $i, j$의 LCA $L = LCA_{C_T}(i, j)$에 대해 $D(L, i) + D(L, j)$입니다.
  • $D(i, j)$는 $T$의 Centroid Tree $C_T$에서 $i, j$의 공통 조상 $P$에 대해 $D(i, j) \leq D(P, i) + D(P, j)$를 만족합니다.

이 두 사실을 잘 기억하고 있으면 풀이는 상당히 쉽게 나옵니다.

$T_1, T_2$의 Centroid Tree $C_{T_1}, C_{T_2}$를 만듭시다. $C_{T_1}$에서 어떤 정점 $v$를 루트로 하는 서브 트리 내에서의 정답을 모두 구하는 방법을 알아봅시다.
서브 트리 내에서 $v$의 자손 $c$의 정답은, 서브 트리 내에 있는 또 다른 정점 $x$에 대해 $D_1(c, v) + D_1(v, x) + D_2(v, x)$ 이하가 됩니다. 만약 $C_{T_2}$에서 $x$의 모든 조상 $y$를 순회한다면 $D_1(c, v) + D_1(v, x) + D_2(v, y) + D_2(y, x)$를 계산해도 됩니다.
그러므로 $C_{T_1}$에서 $v$의 자손 $x$에 대해 $C_{T_2}$에서 $x$의 조상 $y$에 $D_1(v, x) + D_2(y, x)$의 최솟값을 저장한 뒤, 다시 $C_{T_1}$에서 $v$의 자손 $c$마다 $C_{T_2}$에서 $c$의 조상 $p$를 순회하면서 정답을 갱신하면 됩니다. (($p$에 저장된 최솟값)$+ D_1(c, v) + D_2(p, c)$ 갱신)

$C_{T_1}$에서 $v$를 루트로 하는 서브 트리의 크기를 $S_v$라고 할 때, $v$의 서브 트리 내에서의 정답은 $O(S_v \log N)$ 시간에 구할 수 있습니다. Centroid Tree에서 $\sum S_v \in O(N \log N)$이므로 $O(N \log^2 N)$에 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PLL = pair<ll, ll>;
constexpr ll SZ = 152525, INF = 0xc03f3f3f3f3f3f3f;

struct MinPair{
    PLL V[2];
    MinPair(){ V[0] = V[1] = PLL(INF, -1); }
    void clear(){ V[0] = V[1] = PLL(INF, -1); }
    void update(const PLL v){
        if(V[0] > v) V[1] = V[0], V[0] = v;
        else if(V[1] > v) V[1] = v;
    }
    const PLL& operator [] (int idx) const { return V[idx]; }
};

int N, S[SZ], U[SZ];
vector<PLL> G[2][SZ];
vector<PLL> cInfo[SZ], pInfo[SZ];
MinPair Small[SZ];
ll R[SZ];

void add_edge(int id, int s, int e, int x){
    G[id][s].emplace_back(e, x);
    G[id][e].emplace_back(s, x);
}
int get_sz(int id, int v, int b){
    S[v] = 1;
    for(auto i : G[id][v]) if(!U[i.x] && i.x == b) S[v] += get_sz(id, i.x, v);
    return S[v];
}
int get_cent(int id, int v, int tot, int b){
    for(auto i : G[id][v]) if(!U[i.x] && i.x == b && S[i.x]*2 > tot) return get_cent(id, i.x, tot, v);
    return v;
}
void gather(int id, int rt, int v, int b, int d, ll c){
    if(!id) cInfo[rt].emplace_back(v, c);
    else pInfo[v].emplace_back(rt, c);
    for(auto i : G[id][v]) if(!U[i.x] && i.x != b) gather(id, rt, i.x, v, d+1, c+i.y);
}
void cd(int id, int v){
    int cent = get_cent(id, v, get_sz(id, v, -1), -1);
    gather(id, cent, cent, 0, 0, 0);
    U[cent] = 1;
    for(auto i : G[id][cent]) if(!U[i.x]) cd(id, i.x);
    U[cent] = 0;
}

void Go(int v){
    for(auto i : cInfo[v]) for(auto j : pInfo[i.x]) Small[j.x].clear();
    for(auto i : cInfo[v]) for(auto j : pInfo[i.x]) Small[j.x].update({i.y+j.y, i.x});
    for(auto i : cInfo[v]) for(auto j : pInfo[i.x]) {
        if(Small[j.x][0].y != i.x) R[i.x] = min(R[i.x], i.y + j.y + Small[j.x][0].x);
        if(Small[j.x][1].y != i.x) R[i.x] = min(R[i.x], i.y + j.y + Small[j.x][1].x);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1,s,e,x; i<N; i++) cin >> s >> e >> x, add_edge(0, s, e, x);
    for(int i=1,s,e,x; i<N; i++) cin >> s >> e >> x, add_edge(1, s, e, x);
    cd(0, 1);
    cd(1, 1);
    memset(R, 0x3f, sizeof R);
    for(int i=1; i<=N; i++) Go(i);
    for(int i=1; i<=N; i++) cout << R[i] << "\n";
}