题解 P5021 【赛道修建】

· · 题解

终于从普及-->提高啦

首先由最小值最大得出这道题的做法是二分答案

由此我们把题目简化成了求无根树上大于等于某长度的链数量是否等于m

判断有两种方法，个人倾向于multiset，时间复杂度较低

判断的思路：贪心，由u点出发如果已经大于要判断的长度，则大于x的数量加1；否则把他放入multiset中，然后一一配对

附上判断的代码

inline ll dfs(int u,int fa,ll x){
    s[u].clear();
    ll mv=0;    
    //如果边大于x直接加入答案，否则把它加入到multiset的集合之中
    for(int i=head[u],v;i;i=edge[i].nxt){
        v=edge[i].v;
        if(v==fa)continue;
        mv=dfs(v,u,x)+edge[i].w;
        if(mv>=x)
            ans++;
        else 
            s[u].insert(mv);
    }
    ll l_len=0,res;
    //进行每条边的配对，如果无法配对就把他erase掉
    while(!s[u].empty()){
        res=*s[u].begin();
        if(s[u].size()==1){
            return MAX(l_len,res);
        }
        it=s[u].lower_bound(x-res);
        if(it==s[u].begin()&&s[u].count(*it)==1)it++;
        if(it==s[u].end()){
            l_len=MAX(l_len,res);
            s[u].erase(s[u].find(res));
        }
        else {
            ans++;
            s[u].erase(s[u].find(res));
            s[u].erase(s[u].find(*it));
        }
    }
    return l_len;
}

inline bool check(int x){
    ans=0;
    dfs(1,0,x);
    return ans>=m;
}

如何确定[l,r],l和r的值，显而易见r最大的值就是数的直径，并且也可以由此特判m=1的情况输出答案，而l的值则是最小的w[i],附上求直径代码

inline void dfss(int u,int fa){
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==fa)continue;
        dis[v]=dis[u]+edge[i].w;
        if(dis[v]>mx){
            cur=v;mx=dis[v];
        }
        dfss(v,u);
    }
}

inline ll maxlen(){
    dfss(1,0);
    memset(dis,0,sizeof(dis));
    mx=0;
    dfss(cur,0);
    return mx;
}

完整代码如下

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read(){
    ll x=0,f=1;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}

const int maxn=50000 + 5;

ll n,m;

struct Edge{
    int nxt,v,w;
}edge[maxn<<1];

ll cnt,head[maxn];

#define MAX(a,b)(a>b?a:b)

#define MIN(a,b)(a>b?b:a)

inline void addedge(int u,int v,int w){
    edge[++cnt].nxt=head[u];
    edge[cnt].w=w;
    edge[cnt].v=v;
    head[u]=cnt;
}

ll dis[maxn],up,cur;

ll l_len,ans,l,r;

/*inline ll dfs1(int u,int fa){
    int sum1=0,sum2=0;
    for(int i=head[u];i;i=edge[i].nxt){
        ll v=edge[i].v;
        if(v==fa) continue;
        sum2=MAX(sum2,dfs1(v,u)+edge[i].w);
        if(sum1<sum2) swap(sum1,sum2);
    }
    up=MAX(up,sum1+sum2);
    return sum1;
}*/

ll mx=-1e8;

inline void dfss(int u,int fa){
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==fa)continue;
        dis[v]=dis[u]+edge[i].w;
        if(dis[v]>mx){
            cur=v;mx=dis[v];
        }
        dfss(v,u);
    }
}

inline ll maxlen(){
    dfss(1,0);
    memset(dis,0,sizeof(dis));
    mx=0;
    dfss(cur,0);
    return mx;
}

multiset<ll>s[maxn];
multiset<ll>::iterator it;

inline ll dfs(int u,int fa,ll x){
    s[u].clear();
    ll mv=0;    
    //如果边大于x直接加入答案，否则把它加入到multiset的集合之中
    for(int i=head[u],v;i;i=edge[i].nxt){
        v=edge[i].v;
        if(v==fa)continue;
        mv=dfs(v,u,x)+edge[i].w;
        if(mv>=x)
            ans++;
        else 
            s[u].insert(mv);
    }
    ll l_len=0,res;
    //进行每条边的配对，如果无法配对就把他erase掉
    while(!s[u].empty()){
        res=*s[u].begin();
        if(s[u].size()==1){
            return MAX(l_len,res);
        }
        it=s[u].lower_bound(x-res);
        if(it==s[u].begin()&&s[u].count(*it)==1)it++;
        if(it==s[u].end()){
            l_len=MAX(l_len,res);
            s[u].erase(s[u].find(res));
        }
        else {
            ans++;
            s[u].erase(s[u].find(res));
            s[u].erase(s[u].find(*it));
        }
    }
    return l_len;
}

inline bool check(int x){
    ans=0;
    dfs(1,0,x);
    return ans>=m;
}

inline void work(){
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    printf("%lld\n",l);
}

int main(){
    n=read();m=read();
    for(int i=1,a,b,ll;i<n;i++){
        a=read();b=read();ll=read();
        r+=ll;
        addedge(a,b,ll);
        addedge(b,a,ll);
    }
    ll l=1,r=maxlen();
    if(m==1){
        printf("%lld\n",r);
        return 0;
    }
    work();
    return 0;
}