题目描述
调查兵团第56次壁外调查将对巨木之森展开，已知巨木之森共有n块区域和n-1条道路，保证这n块区域联通。为了调查结果尽可能准确，兵团会派遣若干支小分队调查巨木之森，派出的小分队需满足以下规定：

1.每支小分队都可以选择从任意一块区域出发，但各支小分队的出发区域必须互不相同。

2.每支小分队都必须遍历完nn块区域。

3.每支小分队的物资消耗量为其遍历完nn块区域的路程和。

现已知调查兵团的物资总量为mm，请问最多能派遣多少支小分队参与调查？

思路：对于树来说，遍历所有点回到出发点每条边要经过两边，花费是所有边的权值和乘以二假设为sum。然后小分队从某一点出发到达某个目的点，两点之间最短路上的边只需要经过一次，所以花费就是sum减去最短路上边的权值，为使花费最少，就需要找到距离该点最远的点也就是树的直径的某个端点。那么做法就出来了，找到树的直径的端点（先从1搜一遍找到最远的端点，再从该点搜一遍找到最远的端点，这两个端点的最短路就是直径），然后枚举所有点，求出每一点的最小花费存入数组，再sort一遍，找到最小的那几个花费，就是答案了。

代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node{
    int v;
    long long w;
    Node(int vv,long long ww):v(vv),w(ww){}
};
int n;
long long m;
vector<Node>edge[100005];
long long dist[2][100005];
void dfs(int u,int id,int pre,long long dis)
{
    dist[id][u]=dis;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i].v;
        if(v==pre)continue;
        dfs(v,id,u,dis+edge[u][i].w);
    }
}
int main()
{
    scanf("%d%lld",&n,&m);
    long long sum=0;
    for(int i=0;i<n-1;i++){
        int u,v;
        long long w;
        scanf("%d%d%lld",&u,&v,&w);
        edge[u].push_back(Node(v,w));
        edge[v].push_back(Node(u,w));
        sum+=w;
    }
    sum*=2;
    int l,r;
    long long temp=-1;
    dist[0][1]=0;
    dfs(1,0,0,0);
    for(int i=1;i<=n;i++)if(dist[0][i]>temp)temp=dist[0][i],l=i;
    dist[0][l]=0,temp=-1;
    dfs(l,0,0,0);
    for(int i=1;i<=n;i++)if(dist[0][i]>temp)temp=dist[0][i],r=i;
    dist[1][r]=0;
    dfs(r,1,0,0);
    int i;
    long long t=0,a[100005];
    for(i=1;i<=n;i++){
        a[i]=sum-max(dist[0][i],dist[1][i]);
        //printf("%lld\n",a[i]);
    }
    sort(a+1,a+n+1);
    for(i=1;i<=n;i++)
    {
        t+=a[i];
        if(t>m)break;
    }
    printf("%d\n",i-1);
    return 0;
}