CF 1004E Sonya and Ice Cream

题目描述

http://codeforces.com/problemset/problem/1004/E

Solution

能够发现这条路径一定是在直径上，所以我们可以考虑在直径上做一个滑动窗口

但是这样太麻烦了，我们考虑用类似拓扑排序东西来做一个贪心

即从叶子开始删点，并更新每个点向子树内拓展的最大距离

直到删的只剩 $k$ 个点且为一条链

时间复杂度 $O(n\log n)$

#include <iostream>
#include <set>
#include <queue>
#define maxn 100010
using namespace std;

int n, k;

set<pair<int, int>> S[maxn];

struct Queue {
    int k, v;
    
    friend bool operator < (const Queue &u, const Queue &v) { return u.v > v.v; } 
}; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k; 
    for (int i = 1; i < n; ++i) {
        int x, y, z; cin >> x >> y >> z;
        S[y].insert({ x, z });
        S[x].insert({ y, z }); 
    } priority_queue<Queue> Q;
    for (int i = 1; i <= n; ++i)
        if (S[i].size() == 1) Q.push({ i, S[i].begin() -> second });
    int ans = 0;
    while (Q.size() > 2 || k < n) {
        int u = Q.top().k, v; ans = Q.top().v; Q.pop(); --n;
        v = S[u].begin() -> first;
        S[v].erase(S[v].lower_bound({ u, 0 }));
        if (S[v].size() == 1) Q.push({ v, ans + S[v].begin() -> second });
    } cout << ans << "\n";
    return 0;
}