【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\n", ans);

    return 0;

}