In Search of Gold
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6769
解题思路：要求最大值最小，就采用二分的方法来做，最小就是0，最大就是所有边取最大值然后二分这个直径。
但是我们如何求树上的直径使其最大最小，考虑dp的方法来做，dp[i][j]表示在以i为根的子树中选取m条边，经过根i的最长路径最大时，与i向相距最远的节点距离。因此我们只要使得，在dfs的过程种，这个最长路径一直小于mid就可以更新我们的dp数组，最终只要dp[1][k]小于mid则就是一个正确解。
当然我们在dp的过程种，可能会遇到同一最远节点距选两次的情况，因此我们在求解一个子树的过程把要更新的答案占时封存起来，求解完这个子树再更新到最终的数组中。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f; const int maxn=4e5+10; struct no { int to,next; }edge[maxn]; ll head[maxn],cnt,a[maxn],b[maxn],f[maxn][25],size[maxn]; ll n,m,mid,ans; void add(int u,int v,ll f3,ll f4) { edge[cnt].to=v; edge[cnt].next=head[u]; a[cnt]=f3,b[cnt]=f4; head[u]=cnt++; } void init() { cnt=0; memset(head,-1, sizeof(head)); } void dfs(int u,int fa) { size[u]=0; for(int i=0;i<=m;i++) f[u][i]=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v==fa) continue; dfs(v,u); int now=min(size[v]+size[u]+1,m); //now表示最多可以选取的边 ll t[22]; for(int j=0;j<=now;j++) t[j]=mid+1; for(int j=0;j<=size[u];j++) { for(int k=0;k<=size[v]&&j+k<=m;k++) {if(f[u][j]+f[v][k]+a[i]<=mid) t[j+k+1]=min(t[j+k+1],max(f[u][j],f[v][k]+a[i])); //如果选a[i]并且符合条件 if(f[u][j]+f[v][k]+b[i]<=mid) t[j+k]=min(t[j+k],max(f[u][j],f[v][k]+b[i]));} //如果选b[i]并且符合条件 } for(int j=0;j<=now;j++) f[u][j]=t[j]; size[u]=now; } } int main() { int t; scanf("%d",&t); while(t--) { init(); scanf("%lld%lld",&n,&m); ll l=1,r=0; for(int i=1;i<n;i++) { ll f1,f2,f3,f4; scanf("%lld%lld%lld%lld",&f1,&f2,&f3,&f4); add(f1,f2,f3,f4); add(f2,f1,f3,f4); r+=max(f3,f4); } ll ans=r; while(l<=r) { mid=(l+r)/2; dfs(1,0); if(f[1][m]<=mid) ans=mid,r=mid-1; else l=mid+1; } printf("%lld ",ans); } }