链接 : A - 巨木之森
题意： 每支小队从每个点出发 ，遍历完整颗树的花费是走过路径的和，要求在花费 m 以内，最多可以有多少个小队遍历完整颗树。 思路：
可以求出每个点遍历整棵树的花费 ，排个序，从小到大选就好了，关键在于求花费。可以发现，要想遍历完整颗树，再回到原来的位置，那么就要把每条边都走两遍，但是现在不需要回到原来的位置，所以只要找到离根节点最远的点，用总权值的两倍减去 这条最远边的长度就好了。根据树的一个性质，离某个点最远的点一定是树直径两端点中的一个，所以我们只要求出树的直径的两个端点，然后得到其他点到这两个点的距离就好了。代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 7; int head[maxn],num,n,ans,pos; ll sum,w,dis[maxn][2],val[maxn],m; struct node{ ll to,next; ll w; }e[maxn]; void add(ll u,ll v,ll w){ e[num].next = head[u]; e[num].to = v; e[num].w = w; head[u] = num ++; } void dfs(int u,int pre,int id){ if(dis[u][id] > dis[pos][id]) pos = u; for(int i = head[u]; i != -1; i = e[i].next){ ll to = e[i].to; ll w = e[i].w; if(to == pre) continue; dis[to][id] = dis[u][id] + w; dfs(to,u,id); } } int main() { memset(head,-1,sizeof(head)); scanf("%lld%lld",&n,&m); for(ll i = 0,u,v; i < n - 1; i ++){ scanf("%lld%lld%lld",&u,&v,&w); add(u,v,w); add(v,u,w); sum += 2 * w; } pos = 1; dfs(1,-1,0); dis[pos][0] = 0; dfs(pos,-1,0); dfs(pos,-1,1); for(int i = 1; i <= n; i++){ val[i] = sum - max(dis[i][1],dis[i][0]); } sort(val + 1,val + n + 1); ll res = 0; for(int i = 1; i <= n; i++){ if(res+val[i]<=m){ res+=val[i]; ans++; } else break; } printf ("%d\n",ans); }