题目大意:
每一条边都有两个权值,val和路径长度d,要保证在val<=m 的条件下，求最长的d.
解题报告:
一开始想错了，后来发现还不如直接暴力点分，思想很套路..
平时我们统计时，都会用合法减不合法，但这题不是方案统计，需要枚举每一棵子树，这里其实直接暴力枚就行，但是用到了val和d的单调性，首先明确：如果对于两条路径i,j:(vali>valj,di<dj) 这样显然不会最优，所以我们就去掉这些路径，剩下的就满足单调性了，d随val增加而增加，这样就可以二分了.
所以我们把子树分为两个部分，一部分是已经处理好的，另一部分是未知的集合e，我们枚举处理好的集合c，然后将e按val从小到大排序后，二分最大满足(val_c+val_e<=m) 的e，此时的e一定是d最大的，更新答案后，我们再把e加入到c集合中，此时c集合依旧满足单调性.
复杂度(O(TNlog2N))
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define ls (node<<1)
#define rs (node<<1|1)
using namespace std;
const int N=30005,inf=100000005;
int gi(){
int str=0;char ch=getchar();
while(ch>'9' || ch<'0')ch=getchar();
while(ch>='0' && ch<='9')
str=(str<<1)+(str<<3)+ch-48,ch=getchar();
return str;
}
int m,head[N],num=0,to[N<<1],nxt[N<<1],dis[N<<1],c[N<<1],n,ans=0;
int f[N]={inf},root=0,son[N],sum,sz=0,CNT=0;bool vis[N];
void link(int x,int y,int z,int k){
nxt[++num]=head[x];to[num]=y;dis[num]=z;c[num]=k;
head[x]=num;
}
il void getroot(int x,int last){
int u;son[x]=1;f[x]=0;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==last || vis[u])continue;
getroot(u,x);
son[x]+=son[u];
f[x]=Max(f[x],son[u]);
}
f[x]=Max(f[x],sum-son[x]);
if(f[x]<f[root])root=x;
}
struct node{
int d,c;
bool operator<(const node &pp)const{
return d<pp.d;
}
}v[N];
il void getdis(int x,int last,int dist,int cost){
int u;
v[++sz].d=dist;v[sz].c=cost;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==last || vis[u])continue;
getdis(u,x,dist+dis[i],cost+c[i]);
}
}
int q[N][2],tot=0;
void Unique(){
int p=0,mx=0;
sort(v+1,v+sz+1);
for(int i=1;i<=sz;i++){
if(v[i].c<=mx)continue;
else {
v[++p]=v[i];
mx=v[i].c;
}
}
sz=p;
}
int midit(int x){
int l=1,r=sz,mid,ret=-1;
while(l<=r){
mid=(l+r)>>1;
if(x+v[mid].d<=m)ret=mid,l=mid+1;
else r=mid-1;
}
return ret;
}
void cal(){
Unique();
int tmp;
for(int i=1;i<=tot;i++){
tmp=midit(q[i][0]);if(tmp==-1)continue;
if(v[tmp].c+q[i][1]>ans)ans=v[tmp].c+q[i][1];
}
for(int i=1;i<=sz;i++){
q[++tot][0]=v[i].d;q[tot][1]=v[i].c;
}
sz=0;
}
il void solve(int x){
int u;tot=0;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(vis[u])continue;
getdis(u,x,dis[i],c[i]);
cal();
}
}
il void dfs(int x){
int u;vis[x]=true;
solve(x);
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(vis[u])continue;
sum=son[u];root=0;getroot(u,x);
dfs(root);
}
}
void Clear(){
num=0;ans=0;memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
}
void work()
{
Clear();
int x,y,z,r;
n=gi();m=gi();
for(int i=1;i<n;i++){
x=gi();y=gi();z=gi();r=gi();
link(x,y,z,r);link(y,x,z,r);
}
root=0;sum=n;getroot(1,1);
dfs(root);
printf("Case %d: %d
",CNT,ans);
}
int main()
{
int T=gi();
while(T--)CNT++,work();
return 0;
}