백준15928 Growing Trees

작성일 | In

문제 링크

  • http://icpc.me/15928

사용 알고리즘

  • 삼분 탐색
  • 트리 DP

시간복잡도

  • $O(N \log X)$

풀이

KOI 2016 고등부 4번 먼 별의 트리 버전입니다. 삼분 탐색을 하면서 트리의 지름을 구하면 됩니다.
간선의 가중치가 음수가 될 수 있기 때문에 트리 DP를 이용해서 지름을 구해야 합니다.

전체 코드

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
#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 INF64 = 0x3f3f3f3f3f3f3f3f;

struct Edge{
    int v, c, a;
    Edge() = default;
    Edge(int v, int c, int a) : v(v), c(c), a(a) {}
};

ll N, K;
vector<Edge> G[252525];

ll D[252525][2];
void Update(int v, ll val){
    if(val > D[v][0]) D[v][1] = D[v][0], D[v][0] = val;
    else if(val > D[v][1]) D[v][1] = val;
}
void DFS(ll day, int v, int b=-1){
    D[v][0] = 0; D[v][1] = -INF64;
    for(auto [i,c,a] : G[v]){
        if(i == b) continue;
        DFS(day, i, v);
        Update(v, D[i][0] + c + a * day);
    }
}

ll Check(ll day){
    DFS(day, 1);
    ll res = 0;
    for(int i=1; i<=N; i++) res = max(res, D[i][0] + D[i][1]);
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1; i<N; i++){
        int s, e, c, a; cin >> s >> e >> c >> a;
        G[s].emplace_back(e, c, a);
        G[e].emplace_back(s, c, a);
    }
    int s = 0, e = K;
    while(s + 3 <= e){
        int l = (s + s + e) / 3, r = (s + e + e) / 3;
        if(Check(l) > Check(r)) s = l;
        else e = r;
    }
    ll mn = INF64, idx = s;
    for(int i=s; i<=e; i++){
        ll now = Check(i);
        if(now < mn) mn = now, idx = i;
    }
    cout << idx << "\n" << mn;
}