巨木之森

举个例子：4号点出发，走到2号点结束
由图可得，每个点的代价即为每条边边权*2（红色边和蓝色边）-他走到另一个点的距离（蓝色边），由贪心显然当他走到离他最远的点时最优，此时的问题已经转换为在时间范围内求出每个点到他的最远点的距离，由树的直径的性质可知，这条直径的两个端点中必有一个是每个点的最远端，所以只需求出任一条直径的两个端并算出两点到所有点的距离然后贪心的按代价从小到大选取点即可

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
int read()
{
    int s=0,bj=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return bj?-s:s;
}
void printnum(int x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(int x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
int n,m,sum;
struct node{int nx,to,v;}w[200005];int h[100005],cnt;
void AddEdge(int x,int y,int z)
{
    w[++cnt].to=y;w[cnt].nx=h[x];w[cnt].v=z;h[x]=cnt;sum+=z;
    w[++cnt].to=x;w[cnt].nx=h[y];w[cnt].v=z;h[y]=cnt;
}
int dis[2][100005],maxx,num;
int tot[100005];
void DFS(int x,int fa,int no,bool bj)
{
    dis[bj][x]=no;if(dis[bj][x]>maxx){maxx=dis[bj][x];num=x;}//找直径 
    for(int i=h[x];i;i=w[i].nx)
    {
        int y=w[i].to;
        if(y^fa)DFS(y,x,no+w[i].v,bj);
    }
}
signed main()
{
    int x,y,z;
    n=read();m=read();
    for(int i=1;i<n;++i){x=read();y=read();z=read();AddEdge(x,y,z);}sum<<=1;//每条边要经过两次 
    DFS(1,0,0,0);//搜索直径第一个端点 
    maxx=0;DFS(num,0,0,0);//搜索直径第二个端点并计算第一个端点到各点的距离 
    maxx=0;DFS(num,0,0,1);//计算第二个端点到各点的距离 
    for(int i=1;i<=n;++i)tot[i]=sum-max(dis[0][i],dis[1][i]);//找到每一个点到其他点的最大距离，作为他少走的边，算出以该点开始的代价 
    sort(tot+1,tot+n+1);//代价按从小到大排序 
    for(int i=1;i<=n;++i)
    if(tot[i]<=m)m-=tot[i];
    else {print(i-1,'\n');return 0;}
    print(n,'\n');
    return 0;
}