XG Zepto

题解 P5021 【赛道修建】

2018-11-13 15:21:35


首发于 个人博客

思路

我就顺着我考场上的思路,把所有部分分都讲一讲吧。

首先对于 $m=1$ 的数据,我们显然只要找到直径长度就行;

对于一条链的情况,二分答案,对于每次二分出来的 $mid$ ,从根开始贪心选取一段边,累计长度大于等于 $mid$ 的时候就计入答案,重新开始寻找下一段,得出对于 $mid$ 最大的答案,判断它是否大于 $m$ ;

对于菊花图,由于路径最多经过两条边,我们实质上是要在 $n-1$ 条边中选一共 $m$ 次,每次选出一条独立的边,或者一对边,使得最终每条边的长度 / 每对边的长度和尽量大。对于每次二分出来的 $mid$ ,长度大于 $mid$ 的边独立地选出,而小于 $mid$ 的边尝试一长一短两两配对,用双指针在排过序的长度数据中扫描一遍,得出对于 $mid$ 最大的答案,判断它是否大于 $m$ ;

对于 “分支不超过 3” 的图,也就是除根节点之外,每个点只有两个儿子,同样我们二分答案。首先定义几个概念,我们称从一条赛道两端点 $LCA$ 开始的,到一个端点结束的链为对应赛道的半链,令 $f_i$ 为以 $i$ 为 $LCA$ 的最优半链长度。暂时不考虑根节点,如果 $i$ 只有一个儿子 $v$ ,若 $f_v + l_i \geq mid$ ,直接将 $f_v + l_i$ 计入答案,否则, $f_i = f_v + l_i$ ;如果 $i$ 有两个儿子,如果它们可以直接单独计入答案则直接计入,否则考虑是否可以将这两个儿子牵引的两条半链合并,合并后长度大于 $mid$ 则直接计入答案,否则选取最长的一段转移到 $f_i$ ,对于可能有三个儿子的根节点,遵循的原则同样是尽量独立选取两个儿子,否则尝试合并两条半链计入答案;

如果我们结合菊花图和 “分支不超过 3” 的图这两种情况,我们就可以搞定 100% 的数据。继承上面半链和 $f_i$ 的定义,我们要做的是在使最多的儿子对答案做出贡献的同时,尽量大地将 $f_{son}$ 的值转移给 $f_i$ 。因为 $f$ 的一个值最多对答案产生 1 的贡献,所以使儿子做出更少贡献,转移更大的 $f_i$ 不可能使答案变优,我们的贪心第一关键字就可以设为使儿子做出最大的贡献。在菊花图的算法中,我们只满足了第一个条件,但不需要考虑 $f_i$ 进一步的转移,而我认为这一点正是 A 掉本题的重点。也就是说,我们要在儿子的 $f$ 值中,选出一个最优的转移至 $f_i$ ,使得剩下的 $f$ 值的合法匹配最多。同样可以二分转移至 $f_i$ 的儿子,剩下的和菊花图的做法相同。

总结一下正解:首先二分答案,贪心计算对于 $mid$ 的最大可能答案,判断它和 $m$ 的大小。我们称从一条赛道两端点 $LCA$ 开始的,到一个端点结束的链为对应赛道的半链,令 $f_i$ 为以 $i$ 为 $LCA$ 的最优半链长度。要求对于 $i$ 所有儿子的 $f$ ,在保证两两匹配数(两个半链合成一条赛道)最多的同时,向 $f_i$ 转移尽可能大的值。于是将所有 $f$ 排序贪心找到最大匹配数,然后,二分找到转移给 $f_i$ 的值。

复杂度不太会证,应该接近 $\Theta(n\log n \log \dfrac{\sum{l_i}}{m})$ 吧。

代码

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define ll long long
#define maxn 50010
using namespace std;
struct Edge{
    int to,next,val;
    Edge(int a=0,int b=0,int c=0){
        to=a,next=b,val=c;
    }
}l[maxn<<1];
int head[maxn],cnt,n,m;
vector<int> son[maxn];
ll f[maxn];
int subans[maxn];
void Add(int a,int b,int c){
    l[++cnt]=Edge(b,head[a],c);
    head[a]=cnt;
}
int check(int u,int pos,int tot,ll x){
    int res=0,l=0;
    for (register int r=tot-1;r;--r){
        r-=r==pos;
        while (l<r&&son[u][l]+son[u][r]<x) ++l;
        l+=l==pos;
        if (l>=r) break;
        ++res;++l;
    }
    return res;
}
void Dfs(int u,int fa,ll x){
    f[u]=subans[u]=0;
    son[u].clear();
    for (register int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (v==fa) continue;
        Dfs(v,u,x);
        f[v]+=l[i].val;
        if (f[v]>=x) subans[u]++;
        // 如果已经大于 x 则直接计入答案
        else son[u].push_back(f[v]);
    }
    int tot=son[u].size();
    sort(son[u].begin(),son[u].end());
    int l=0,r=tot,sub=0,res;
    for (register int r=tot-1;r;--r){
        while (l<r&&son[u][l]+son[u][r]<x) ++l;
        if (l>=r) break;
        ++sub;++l;
    }
    subans[u]+=sub;
    // 贪心找出最大的匹配数(两个半链合成一条赛道)
    if (sub*2==tot) return;
    l=0,r=tot-1;
    while(l<=r){
        int tem=check(u,mid,tot,x);
        if (tem==sub) res=mid,l=mid+1;
        else r=mid-1;
    }
    // 二分找到满足最大匹配的,可以转移给 f_u 的最大值
    f[u]=son[u][res];
}
bool check(ll x){
    int tem=0;
    Dfs(1,0,x);
    for (register int i=1;i<=n;++i)
        tem+=subans[i];
    return tem>=m;
}
int main(){
    ll l=0,r=0,ans,c;
    scanf("%d%d",&n,&m);
    for (register int i=1,a,b;i<n;++i)
        scanf("%d%d%lld",&a,&b,&c),
        Add(a,b,c),Add(b,a,c),r+=c;
    r/=(ll)m;
    // 在这里二分答案
    while(l<=r){
        if (check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}