牛客 6874 A

牛客 6874 A

链接 : A - 巨木之森

题意：
每支小队从每个点出发 ，遍历完整颗树的花费是走过路径的和，要求在花费 m 以内，最多可以有多少个小队遍历完整颗树。
思路：

1. 可以求出每个点遍历整棵树的花费 ，排个序，从小到大选就好了，关键在于求花费。
2. 可以发现，要想遍历完整颗树，再回到原来的位置，那么就要把每条边都走两遍，但是现在不需要回到原来的位置，所以只要找到离根节点最远的点，用总权值的两倍减去 这条最远边的长度就好了。
3. 根据树的一个性质，离某个点最远的点一定是树直径两端点中的一个，所以我们只要求出树的直径的两个端点，然后得到其他点到这两个点的距离就好了。

代码：

#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 ("%dn",ans);
}