题意，给你一棵n个点的树，n<=20000。每个边上有两种权值，要求有K条边选第一种权值，n-K-1条边选第二种权值，问树的直径最小是多少。
一开始的想法是设F[x][y]为x的子树中共y个边选了第一种权值时最长链最小为多少。直接DP求解。但是在节点上合并的时候会出现问题。因为不一定这K条边都在直径上，有可能为了凑这K条边使得直径在别的子树里。
所以我们考虑二分答案。
我们设二分之后的答案为mid,那么我们只要在转移F[x][y]的时候，要求无法形成大于mid的链，在最后检测F[1][K]是否有意义且小于等于mid即可。
1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define N 20005 8 #include<ctime> 9 using namespace std; 10 int T,n,K,zz,a[N]; 11 struct ro{ 12 int to,next,a,b; 13 }road[N*2]; 14 void build(int x,int y,int aa,int bb) 15 { 16 zz++; 17 road[zz].to=y; 18 road[zz].a=aa; 19 road[zz].b=bb; 20 road[zz].next=a[x]; 21 a[x]=zz; 22 } 23 int fa[N],A[N],B[N],size[N]; 24 void dfs1(int x) 25 { 26 size[x]=1; 27 for(int i=a[x];i;i=road[i].next) 28 { 29 int y=road[i].to; 30 if(y==fa[x])continue; 31 fa[y]=x; 32 dfs1(y); 33 size[x]+=size[y]; 34 A[y]=road[i].a; 35 B[y]=road[i].b; 36 } 37 } 38 long long F[N][23],tmp[23]; 39 void dfs2(int x,long long da) 40 { 41 for(int i=0;i<=K&&i<=size[x];i++) F[x][i]=0; 42 for(int i=a[x];i;i=road[i].next) 43 { 44 int y=road[i].to; 45 if(y==fa[x])continue; 46 dfs2(y,da); 47 } 48 int cnt=0; 49 for(int i=a[x];i;i=road[i].next) 50 { 51 int y=road[i].to; 52 if(y==fa[x])continue; 53 cnt++; 54 if(cnt==1) 55 { 56 for(int j=0;j<=K;j++) 57 { 58 if(F[y][j])F[x][j]=F[y][j]; 59 } 60 continue; 61 } 62 for(int j=0;j<=K;j++) tmp[j]=1e17; 63 for(int j=0;j<=K;j++) 64 { 65 if(F[x][j]==0)continue; 66 for(int k=0;k+j<=K&&k<=size[y];k++) 67 { 68 if(F[y][k]==0)continue; 69 if(F[y][k]+F[x][j]>da) continue; 70 tmp[j+k]=min(tmp[j+k],max(F[x][j],F[y][k])); 71 } 72 } 73 for(int j=0;j<=K;j++) 74 { 75 if(tmp[j]!=1e17) F[x][j]=tmp[j]; 76 else F[x][j]=0; 77 } 78 } 79 80 if(x!=1) 81 { 82 for(int j=K;j;j--) 83 { 84 if(F[x][j]&&F[x][j-1]) 85 { 86 F[x][j]=min(F[x][j]+B[x],F[x][j-1]+A[x]); 87 } 88 else if(F[x][j-1]) 89 { 90 F[x][j]=F[x][j-1]+A[x]; 91 } 92 else if(F[x][j]) 93 { 94 F[x][j]+=B[x]; 95 } 96 } 97 if(!cnt) 98 { 99 F[x][0]=B[x]; 100 if(K) F[x][1]=A[x]; 101 102 } 103 else if(F[x][0]) 104 { 105 F[x][0]+=B[x]; 106 } 107 } 108 109 } 110 int main() 111 { 112 scanf("%d",&T); 113 while(T--) 114 { 115 zz=0; 116 scanf("%d%d",&n,&K); 117 for(int i=1;i<=n;i++) 118 { 119 fa[i]=A[i]=B[i]=a[i]=0; 120 for(int j=0;j<=K;j++) F[i][j]=0; 121 } 122 for(int i=1;i<n;i++) 123 { 124 int x,y,a,b; 125 scanf("%d%d%d%d",&x,&y,&a,&b); 126 build(x,y,a,b); 127 build(y,x,a,b); 128 } 129 long long li,ri,mid,ans=-1; 130 li=1,ri=1e14; 131 dfs1(1); 132 while(li<=ri) 133 { 134 mid=(li+ri)>>1; 135 dfs2(1,mid); 136 if(F[1][K]&&F[1][K]<=mid) 137 { 138 ans=mid; 139 ri=mid-1; 140 } 141 else li=mid+1; 142 } 143 printf("%lld ",ans); 144 } 145 return 0; 146 }