題目鏈接

problem

給出一棵有邊權的樹。一條鏈的權值定義為該鏈所經過的邊的邊權值和。需要選出\(m\)條鏈，求\(m\)條鏈中權值最小的鏈的權值最大是多少。

solution

首先顯然二分。

然後考慮如何判斷二分出來的一個答案\(x\)是否是可行的。也就是能否選出\(m\)條鏈，每條鏈權值都大於等於\(x\)。這個其實是貪心。

定義直鏈為從一個某個點的祖先到該點的路徑。

可以發現每條鏈要麼就是一條直鏈，要麼由兩條直鏈在某個點處合併起來得到。

貪心的地方在於，對於每個點肯定都是優先將能合成的直鏈合成。然後再保證向上傳遞的直鏈長度最大。因為即便向上傳遞的長度特別大，產生的貢獻也做多只能是\(1\)。所以要先保證在當前子樹上合成最多的鏈。

然後問題就變成了在一棵子樹內得到一些直鏈長度。現在把這些直鏈兩兩合併成權值大於等於\(x\)的鏈。然後保證剩下的直鏈長度最大。

這裡可以二分答案一下。也可以用個\(multiset\)處理。反正是很可做的一個問題。

代碼中有各檔部分分,BF5為正解

code

#include<set>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int n,m;
struct node {
    int v,nxt,w;
}e[N << 1];
int head[N],ejs;
void add(int u,int v,int w) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
}
namespace BF1 {
    int dis[N];
    void dfs(int u,int fa) {
        for(int i = head[u];i;i = e[i].nxt) {
            int v = e[i].v;
            if(v == fa) continue;
            dis[v] = dis[u] + e[i].w;
            dfs(v,u);
        }
    }
    void main() {
        dfs(1,0);
        int x = 0;
        for(int i = 1;i <= n;++i) if(dis[i] > dis[x]) x = i;
//      cout<<x<<endl;
        memset(dis,0,sizeof(dis));
        dfs(x,0);
        int ans = 0;
        for(int i = 1;i <= n;++i) ans = max(ans,dis[i]);
        cout<<ans;
    }
}

namespace BF2 {
    int a[N],cnt;
    int check(int x) {
        int p = 1,ret = 0;
        for(int i = cnt;i > p;--i) {
            if(a[i] > x && i > p) {ret++;continue;}
            while(a[p] + a[i] < x && p < i) ++p;
            if(p < i) ret++,p++;
            else break;
        }
        return ret;
    }
    void main() {
        int l = 100000,r = 0;
        for(int i = 1;i <= ejs;i += 2) a[++cnt] = e[i].w,l = min(l,a[cnt]),r += a[cnt];
        sort(a + 1,a + cnt + 1);

        int ans = 0;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(check(mid) >= m) ans = mid,l = mid + 1;
            else r = mid - 1;
        }
        cout<<ans<<endl;
    }
}
int du[N];
namespace BF3 {
    
    int a[N],cnt;
    void dfs(int u,int fa) {
        for(int i = head[u];i;i = e[i].nxt) {
            int v = e[i].v;
            if(v == fa) continue;
            a[++cnt] = e[i].w;
            dfs(v,u);
        }
    }
    int check(int x) {
        int now = 0,ret = 0;
        for(int i = 1;i <= cnt;++i) {
            now += a[i];
            if(now >= x) now = 0,ret ++;
        }
        return ret;
    }
    void main() {
        for(int i = 1;i <= n;++i) 
            if(du[i] == 1) {dfs(i,0);break;}
        int l = 1000000,r = 0;
        for(int i = 1;i <= ejs;i += 2) {
            l = min(l,e[i].w);r += e[i].w;
        }
        
        int ans = 0;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(check(mid) >= m) ans = mid,l = mid + 1;
            else r = mid - 1;
        }
        cout<<ans<<endl;
        
    }

}
int L = 100000,R;
namespace BF5 {
    int ANS;
    int dfs(int u,int fa,int x) {
        multiset<int>s;
        int ret = 0;
//      if(!s.empty()) printf("%d\n",u);
        for(int i = head[u];i;i = e[i].nxt) {
            int v = e[i].v;
            if(v == fa) continue;
            int k = dfs(v,u,x);
            if(k + e[i].w >= x) ANS++;
            else s.insert(k + e[i].w);
        }
        while(!s.empty()) {
            multiset<int>::iterator it = s.begin();
            int k = *it;
            s.erase(it);
            multiset<int>::iterator is = s.lower_bound(x - k);
            if(is == s.end()) ret = max(ret,k);
            else ANS++,s.erase(is);
        }
//      s.clear();
        
//      printf("%d %d\n",u,ret);

        return ret;
    }
    void main() {
        int l = L,r = R,ans = 0;
        
        while(l <= r) {

            int mid =(l + r) >> 1;
            ANS = 0;dfs(1,0,mid);
            if(ANS >= m) ans = mid,l = mid + 1;
            else r = mid - 1;
        }
        cout<<ans;
    }
}
int main() {
    n = read(),m = read();
    int bz1 = 1,bz2 = 1;
    for(int i = 1;i < n;++i) {
        int u = read(),v = read(),w = read();
        L = min(L,w);R += w;    
        du[u]++;du[v]++;
    
        add(u,v,w);add(v,u,w);
        if(u != 1) bz1 = 0;
        if(v != u + 1) bz2 = 0;
    }
    
    if(m == 1) {BF1::main();return 0;}
    if(bz1) {BF2::main();return 0;}
    if(bz2) {BF3::main();return 0;}
    BF5::main();
    return 0;
}
/*
7 1
1 2 10
1 3 5
2 4 9
2 5 8
3 6 6
3 7 7
*/