【题解】LuoGu5021/NOIp2018：赛道修建

原题传送门
蓝题难度吧？怎么上升到紫题了？
考场里，作为一个真·蒟蒻，自然是没想到打满分的，于是疯狂打子任务，于是乎，我把四个子任务都打了。

• $m=1$, 也就是求直径，比赛时我还不知道树的直径这种东西，于是我写了个树形dp，那部分的分数应该拿到了
• $a_i=1$, 也就是菊花图，想到一条赛道最多由两条边组成（根据菊花图的特点），考虑使用二分+头尾指针移动贪心解决，这部分现在觉得考场里也没打错
• $b_i=a_i+1$, 也就是一条链，这种情况也是十分显然的二分+check啦，不过我考场里好像这部分写炸了，丢掉了5分
• 分支不超过3， 想到二分+树形dp，往下最多三条路径，有的路径直接满足要求，计数器+1，有的不能满足要求的则试试看能不能互相组合，最后剩下的作为返回值上传到父节点，其中可以记两个变量表示最大值与次大值方便计算

最终是pascal280行代码拿下75分，十分满意
以下考场代码又臭又长，可以跳过~
Code：

const
    maxn = 200005;
var
    edge : array[0..maxn] of record
        t, len, next : int64;
    end;
    a, dp, head : array[0..maxn] of int64;
    r : array[0..maxn] of record
        a, b, l : int64;
    end;
    ans, num, n, m, tot, stdmid, total : int64;
    i : longint;
    ai1, biai1 : boolean;

function max(x, y : int64) : int64;

begin
    if x > y then exit(x) else exit(y);
end;

procedure add(x, y, z : longint);

begin
    inc(num);
    edge[num].t := y;
    edge[num].len := z;
    edge[num].next := head[x];
    head[x] := num;
end;

procedure swap(var x, y : int64);
var
    tmp : int64;

begin
    tmp := x; x := y; y := tmp;
end;

procedure sort(l, r : longint);
var
    i, j, mid : longint;

begin
    i := l; j := r; mid := a[(l + r) >> 1];
    repeat
        while a[i] < mid do inc(i);
        while a[j] > mid do dec(j);
        if i <= j then
        begin
            swap(a[i], a[j]);
            inc(i); dec(j);
        end;
    until i > j;
    if i < r then sort(i, r);
    if l < j then sort(l, j);
end;

function check(mid : int64) : boolean;
var
    cnt, i : longint;
    sum : int64;

begin
    sum := 0; cnt := 0;
    for i := 1 to tot do
    begin
        inc(sum, a[i]);
        if sum >= mid then
        begin
            sum := 0; inc(cnt);
        end;
    end;
    if cnt >= m then exit(true) else exit(false);
end;

function check2(mid : int64) : boolean;
var
    i, j, k : longint;
    cnt : int64;

begin
    cnt := 0;
    i := n - 1;
    while (a[i] >= mid) and (i >= 1) do
    begin
        inc(cnt); dec(i);
    end;
    if cnt >= m then exit(true);
    k := i;
    for i := 1 to k - 1 do
        if a[i] + a[k] >= mid then break;
    j := i;
    while (j < k) and (a[j] + a[k] >= mid) do
    begin
        inc(cnt);
        dec(k);
        inc(j);
        while (j < k - 1) and (a[j] + a[k] < mid) do inc(j);
    end;
    if cnt >= m then exit(true) else exit(false);
end;

function dfs(u, pre : longint) : int64;
var
    i : longint;
    s, maxf, maxs, v : int64;

begin
    if dp[u] > 0 then exit(dp[u]);
    i := head[u];
    dp[u] := 0;
    maxf := -maxlongint; maxs := maxf;
    while i <> 0 do
    begin
        v := edge[i].t;
        if v <> pre then
        begin
            s := edge[i].len + dfs(v, u);
            dp[u] := max(dp[u], s);
            if s > maxf then
            begin
                maxs := maxf; maxf := s;
            end else
            if s > maxs then maxs := s;
        end;
        i := edge[i].next;
    end;
    ans := max(ans, maxf + maxs);
    exit(dp[u]);
end;

procedure do1;
var
    i : longint;
    x : int64;

begin
    ans := 0;
    x := dfs(1, 0);
    writeln(ans);
end;

procedure do2;
var
    l, rr, ans, mid : int64;
    i : longint;

begin
    tot := n - 1; rr := 0;
    for i := 1 to tot do
    begin
        a[i] := r[i].l;
        inc(rr, a[i]);
    end;
    sort(1, tot);
    l := 0;
    ans := 0;
    while l <= rr do
    begin
        mid := (l + rr) >> 1;
        if check2(mid) then
        begin
            l := mid + 1; ans := mid;
        end else rr := mid - 1;
    end;
    writeln(ans);
end;

procedure do3;
var
    u, l, rr, mid, ans, i : int64;

begin
    u := 1; tot := 0; rr := 0;
    while tot < n - 1 do
    begin
        i := head[u];
        while edge[i].t <> u + 1 do i := edge[i].next;
        inc(tot); a[tot] := edge[i].len; inc(rr, edge[i].len);
        u := edge[i].t;
    end;
    l := 0;
    ans := 0;
    while l <= rr do
    begin
        mid := (l + rr) >> 1;
        if check(mid) then
        begin
            l := mid + 1;
            ans := mid;
        end else rr := mid - 1;
    end;
    writeln(ans);
end;

function dfs1(u, pre : longint) : int64;
var
    maxf, maxs, s, v, i : int64;

begin
    if dp[u] > 0 then exit(dp[u]);
    maxf := -maxlongint; maxs := -maxlongint;
    i := head[u];
    while i <> 0 do
    begin
        v := edge[i].t;
        if v <> pre then
        begin
            s := dfs1(v, u) + edge[i].len;
            if s >= stdmid then
            begin
                inc(total);
            end else
            begin
                if s > maxf then
                begin
                    maxs := maxf; maxf := s;
                end else
                if s > maxs then
                begin
                    maxs := s;
                end;
            end;
        end;
        i := edge[i].next;
    end;
    if maxf + maxs >= stdmid then
    begin
        inc(total); dp[u] := 0;
    end else dp[u] := max(0, maxf);
    exit(dp[u]);
end;

function check3(mid : int64) : boolean;
var
    i : longint;
    x : int64;

begin
    total := 0; stdmid := mid;
    fillchar(dp, sizeof(dp), 0);
    x := dfs1(1, 0);
    if total >= m then exit(true) else exit(false);
end;

procedure do4;
var
    l, rr, mid : int64;
    i : longint;

begin
    l := 0; rr := 1;
    for i := 1 to n - 1 do inc(rr, r[i].l);
    ans := 0;
    while l <= rr do
    begin
        mid := (l + rr) >> 1;
        if check3(mid) then
        begin
            l := mid + 1; ans := mid;
        end else rr := mid - 1;
    end;
    writeln(ans);
end;

begin
    readln(n, m);
    for i := 1 to n - 1 do
    begin
        readln(r[i].a, r[i].b, r[i].l);
        if r[i].a <> 1 then ai1 := true;
        if r[i].b <> r[i].a + 1 then biai1 := true;
        add(r[i].a, r[i].b, r[i].l);
        add(r[i].b, r[i].a, r[i].l);
    end;
    if m = 1 then do1 else
    if not ai1 then do2 else
    if not biai1 then do3 else do4;
end.

今天回过头来一想，诶，还真简单，满分的方法不就是菊花图与分支不超过3的组合吗？
考虑二分答案，然后用树形dp check，dfs中开个数组记下儿子们的返回值，这些返回值用菊花图做法，满足答案要求的直接统计到计数器中，其余的用头尾指针贪心搞定

贪心是正确的，当前的也是最优的，但问题是我们还必须考虑到返回值最优，就是在组成的赛道条数达到最大值的情况下，使返回值（儿子上传给父亲的值，就是当前没用）最大，那么我们可以在若干值中再来个二分（因为满足单调性），得到返回值的最优

Code：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
struct Edge{
	int to, next, len;
}edge[maxn << 1];
int head[maxn], num, tot, cnt, mid, n, a[maxn], m, dp[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void add_edge(int x, int y, int z){ edge[++num].to = y; edge[num].len = z; edge[num].next = head[x]; head[x] = num; }

bool Check(int pos, int r, int tmp){//pos代表返回值的下标，看看没有此返回值的贡献还能不能让赛道条数最优
	int l = 1, sum = 0;
	while (1){
		r -= r == pos;
		while (l < r && a[l] + a[r] < mid) ++l;
		l += l == pos;
		if (l >= r) break;
		++sum, ++l, --r;
	}
	return sum >= tmp;
}

void dfs(int u, int pre){
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) dfs(v, u);
	}
	tot = 0;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) a[++tot] = dp[v] + edge[i].len;
	}//记录下若干返回值
	sort(a + 1, a + 1 + tot);
	while (a[tot] >= mid && tot) ++cnt, --tot;//满足要求的先统计
	int s = tot, l = 1, sum = 0;
	while (1){//贪心求解
		while (l < tot && a[tot] + a[l] < mid) ++l;
		if (l >= tot) break;
		++cnt, --tot, ++l, ++sum;
	}
	l = 1; int r = s, ans = 0; 
	while (l <= r){//二分求最优返回值
		int Mid = (l + r) >> 1;
		if (Check(Mid, s, sum)) ans = Mid, l = Mid + 1; else r = Mid - 1;
	}
	dp[u] = a[ans]; 
}

bool check(){
	cnt = 0;
	dfs(1, 0);
	return cnt >= m;
}

int main(){
	n = read(), m = read();
	int l = 0, r = 0, ans = 0;
	for (int i = 1; i < n; ++i){
		int x = read(), y = read(), z = read();
		add_edge(x, y, z); add_edge(y, x, z);
		r += z;
	}
	while (l <= r){//二分答案
		mid = (l + r) >> 1;
		if (check()) ans = mid, l = mid + 1; else r = mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}