题解 P5021 【赛道修建】

· · 题解

对于最小值最大，考虑二分答案。
设当待检查的答案为k,则问题转化为了一棵树上能否找出至少m条长度大于等于k的路径。
考虑一棵子树对全局答案的贡献，显然有两个方面。
第一是当前子树中能最多能找到的满足要求的路径条数，在以u为根的子树中记为ans_u；第二是连到当前子树的根的路径的长度，记为len_u。

约定有序对(a, b)表示ans_u=a, len_u=b,定义(a, b) < (c, d)为对于同一个子树，贡献为(a, b)时全局答案的最大值<贡献为(c, d)时全局答案的最大值。

直觉告诉我们，应该在最大化ans_u的前提下最大化len_u，原因也很显然，若当前子树贡献的两个状态为A=(a, b), B=(c, d),且a>c，那么B \leq A，因为无论d有多大，最多也只能组成一条满足题意的路径，则(c, d) < (c+1, 0) \leq (a, b)。

考虑如何计算以u为根的子树的贡献。在u的所有儿子v的贡献都已经被计算出来的情况下，显然ans_u可以直接赋值为\sum ans_v，那么只需要考虑
1.如何将len_v组成尽量多的满足题意的路径
2.如何最大化剩下的元素（如果有的话）中最大的一个。

1的做法类似于P1094，用双指针扫一遍就行了。
2可以二分答案，每次删去一个元素后用1的做法计算答案，可以求出在答案不变的情况下能够删去的最大元素。

考场代码

#include <cstdio>
#include <cstring>
#include <algorithm>

#define maxn 50005

int n, m, head[maxn], tail, ans[maxn], len[maxn], arr[maxn], vis[maxn];

struct edge {
    int v,w,next;
}edges[maxn<<1];

void add_edge(int u,int v,int w) {
    edges[++tail].v=v;
    edges[tail].w=w;
    edges[tail].next=head[u];
    head[u]=tail;
}

int calc(int tl, int lim) {
    int p2=1; int ret=0;
    for (int i=tl;i>p2;i--) {
        if (vis[i]) continue;
        while (p2<i&&(arr[p2]+arr[i]<lim||vis[p2])) p2++;
        if (p2<i&&!vis[p2]&&arr[i]+arr[p2]>=lim) ret+=1;
        p2++;
    }return ret;
}

void dfs(int u, int f, int lim) {
    ans[u]=0;
    for (int i=head[u];i;i=edges[i].next) {
        if (edges[i].v==f) continue;
        len[edges[i].v]=edges[i].w;
        dfs(edges[i].v, u, lim);
        ans[u]+=ans[edges[i].v];
    }int tl=0; 
    for (int i=head[u];i;i=edges[i].next) {
        if (edges[i].v==f)continue;
        arr[++tl]=len[edges[i].v];
    }if (tl>0)  {
        std::sort(arr+1,arr+tl+1); arr[0]=0;
        int vl=calc(tl,lim); ans[u]+=vl;
        int lb=0, rb=tl, res;
        while (lb<=rb) {
            int mid=(lb+rb)>>1;
            vis[mid]=1;
            if (calc(tl,lim)==vl){
                res=mid; lb=mid+1;
            }else rb=mid-1;
            vis[mid]=0;
        }len[u]+=arr[res];
    }if (len[u]>=lim) {len[u]=0; ans[u]++;}
//  printf("%d:%d %d\n", u, len[u],ans[u]);
}

int check(int v) {
//  printf("checking:%d\n", v);
    std::memset(ans,0,sizeof(ans));
    std::memset(len,0,sizeof(len));
    dfs(1, 0, v);
    return ans[1]>=m;
}

int main() {
    freopen("track.in","r",stdin);
    freopen("track.out","w",stdout);
    std::memset(vis,0,sizeof(vis));
    tail=0;std::memset(head,0,sizeof(head));
    int l=1; int r=0;
    int u,v,w,ret;
    scanf("%d %d", &n, &m);
    for (int i=1;i<n;++i) {
        scanf("%d %d %d", &u, &v, &w); r+=w;
        add_edge(u, v, w);add_edge(v, u,w);
    }while (l<=r) {
        int mid=(l+r)>>1;
        if (check(mid)) {ret=mid; l=mid+1;}
        else r=mid-1;
    }printf("%d", ret);
    return 0;
}