题目链接

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("%dn",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 %dn",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 */