树上直径

树上直径

定理---树上任意一点的最远点一定是树的直径的端点。

可以发现，要想遍历完整颗树，再回到原来的位置，那么就要把每条边都走两遍，但是现在不需要回到原来的位置，所以只要找到离根节点最远的点，用总权值的两倍减去 这条最远边的长度就好了。

于是，我们可以先以某点dfs，求出这点的最远距离----一定是树直径的是某个端点p。

再以该点p出发，dfs找出另一个端点 q；

最后，再dfs q点求出所有点到q点的距离，之后计算，排序求解即可。

#include<bits/stdc++.h>
//树的深搜 
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, M = 2 * N;ll n, m;
ll d[N];
bool st[N];
int h[N],e[M],ne[M],idx;
ll edge[N];
ll q[N];
ll dis1[N];
ll dis2[N];
void add (int a,int b,ll c)
{e[idx]=b;ne[idx]=h[a];edge[idx] = c;h[a]=idx++;}void dfs(ll dis[],int u,int fa)
{for(int i = h[u] ; i != - 1 ; i = ne[i] ){int j = e[i];if(j == fa) continue;dis[j] = max(dis[j],dis[u] +edge[i] );dfs(dis,j,u);}
}int main()
{memset(h,-1,sizeof h);cin >> n >> m;ll x ,y,z;ll all = 0;for(int i = 1 ; i < n ;i++){cin >> x >> y >> z;all += z;add(x,y,z);add(y,x,z);}int maxv = 1;dfs(dis1,maxv,0);for(int i = 2 ;i <= n ;i++) if(dis1[i] > dis1[maxv]) maxv = i;memset(dis1,0,sizeof dis1);dfs(dis1,maxv,0);int  se = 1;for(int i = 2 ;i <= n ;i++) if(dis1[i] > dis1[se]) se = i;dfs(dis2,se,0);//z = 2;//  cout << all << endl;for(int i = 1 ;i <= n ;i++){q[i] = 2ll * all - max(dis1[i],dis2[i]);}sort(q + 1, q + 1 + n);ll ans = 0;int i = 1;for(;i<=n;i++){if(q[i]>m)break;else m-=q[i];}cout << i - 1 << endl;// cout << i - 1 <<endl;
}