【LG5021】[NOIP2018]赛道修建

题面

洛谷

题解

NOIP之前做过增强版还没做出来(QAQ)

一看到题目中的最大值最小，就很容易想到二分答案

重点是考虑如何(check)

设(dp[x])表示在(x)的子树中未被选过的权值最大的路径权值为多少

对于其子节点(v)，它满足(f[v] + cost[u][v] >= mid)就可以选择

否则再选一条路径和它拼在一起即可

这个过程开个(multiset)可以较简单地做

复杂度(O(nlog_n^2))(常数有点大)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set> 
using namespace std;

inline int gi() {
    register int data = 0, w = 1;
    register char ch = 0;
    while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
    if (ch == '-') w = -1 , ch = getchar();
    while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
    return w * data;
} 
#define MAX_N 50005 
struct Graph { int to, cost, next; } e[MAX_N << 1]; int fir[MAX_N], e_cnt = 0; 
void clearGraph() { memset(fir, -1, sizeof(fir)); e_cnt = 0; } 
void Add_Edge(int u, int v, int w) { e[e_cnt] = (Graph){v, w, fir[u]}; fir[u] = e_cnt++; } 
int N, M, dp[MAX_N], stk[MAX_N], top; 
multiset<int> s; 
multiset<int> :: iterator ite; 
int mid, cnt; 
void dfs(int x, int f) { 
    for (int i = fir[x]; ~i; i = e[i].next) 
        if (e[i].to != f) dfs(e[i].to, x); 
    top = 0; 
	for (int i = fir[x]; ~i; i = e[i].next) { 
	    int v = e[i].to; 
	    if (v == f) continue; 
	    dp[v] += e[i].cost; 
	    if (dp[v] >= mid) ++cnt; else stk[++top] = dp[v]; 
    } 
    sort(&stk[1], &stk[top + 1]); s.clear(); 
    for (int i = 1; i <= top; i++) { 
        ite = s.lower_bound(mid - stk[i]); 
        if (ite != s.end()) s.erase(ite), ++cnt; 
        else s.insert(stk[i]); 
    } 
    dp[x] = s.size() ? *s.rbegin() : 0; 
} 
int main () { 
    clearGraph(); 
    N = gi(), M = gi(); 
    int l = 0, r = 0; 
    for (int i = 1; i < N; i++) { 
        int u = gi(), v = gi(), w = gi(); r += w; 
        Add_Edge(u, v, w), Add_Edge(v, u, w); 
    } 
    int ans = (r = r / M); 
    while (l <= r) { 
        mid = (l + r) >> 1, cnt = 0; 
        dfs(1, 0); 
        if (cnt >= M) ans = mid, l = mid + 1; 
        else r = mid - 1; 
    } 
    printf("%d
", ans); 
    return 0; 
}