树的直径

巨木之森

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
using namespace std;
struct pre {
    ll r;
    ll s;
};
vector<vector<pre>>g;
//vector<ll>f;
vector<vector<ll>>dis;
vector<bool>vis;
ll t = 0;
ll lpoint, rpoint;//保存树的两个端点
void dfs(int x, int y) {
    if (vis[x] == true)return;
    vis[x] = true;
    dis[y][x] = t;
    for (int i = 0; i < g[x].size(); i++) {
        if (vis[g[x][i].r] == false) {
            t += g[x][i].s;
            dfs(g[x][i].r, y);
            t -= g[x][i].s;
        }
    }
}
int main()
{
    ios;
    ll n, m;
    cin >> n >> m;
    g.resize(n + 1);
    ll x, y, s, sum = 0;
    //f.resize(n+1);
    vis.resize(n + 1);
    dis.resize(2, vector<ll>(n + 1));
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y >> s;
        g[x].push_back({ y,s });
        g[y].push_back({ x,s });
        sum += s;
    }
    sum *= 2;//总长度*2
    //找到第一个端点
    dfs(1, 0);
    fill(vis.begin(), vis.end(), false);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dis[0][i] > ans) {
            ans = dis[0][i];
            lpoint = i;//第一个端点为最远的那个
        }
    }
    dfs(lpoint, 0);//找到第二个端点&把第一个端点到各个点的值存在dis[0]中
    fill(vis.begin(), vis.end(), false);
    ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dis[0][i] > ans) {
            ans = dis[0][i];
            rpoint = i;
        }
    }
    dfs(rpoint, 1);//把第二个端点到各个点的值存在dis[1]中
    vector<ll>p;
    for (int i = 1; i <= n; i++) {
        p.push_back({ sum - max(dis[0][i],dis[1][i]) });//各个点遍历所要最小资源数
    }
    sort(p.begin(), p.end());
    ll q = 0;
    for (int i = 0; i < p.size(); i++) {
        if (m >= p[i]) {
            m -= p[i];
            q++;
        }
        else break;
    }
    cout << q;
}