A 巨木之森

分析

先有一个思路，考虑一个点的答案记录。因为除了起始节点之间的路径，其它的路径都要经过两次。所以一个节点的答案为 ， 表示总路径的长度， 表示从节点 开始的最长路径。现在就只需要考虑快速算出所有的节点的答案，这里我们抛出一个引理:对于树上的每个节点，距离他最远的点一定是树的直径的某一个端点。这里也非常好证明，考虑反证法，若不为直径一端点，考虑两条路径相交、不相交两种情况，可以证明出一定有比直径更长的路径。所以只要求出一个节点到直径端点的距离就可以了。时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
LL read() {LL x;scanf("%lld",&x);return x;}
const int N = 1e5+100;
vector<LL> W[N],G[N];
LL ans[N];
LL f[N],dis[N],dis2[N],dep[N],rt,rt2,n,m,sum;
void dfs(int x,int fa,LL Dep) {
    dep[x] = Dep;
    for(int i = 0;i < G[x].size();i++) {
        int y = G[x][i];
        if(y == fa) continue;
        dfs(y,x,Dep+W[x][i]);
    }
    if(dep[rt] < dep[x]) rt = x;
}
void dfs1(int x,int fa,LL Dep) {
    dis[x] = Dep;
    for(int i = 0;i < G[x].size();i++) {
        int y = G[x][i];
        if(y == fa) continue;
        dfs1(y,x,Dep+W[x][i]);
    }    
    if(dis[rt2] < dis[x]) rt2 = x;
}
void dfs2(int x,int fa,LL Dep) {
    dis2[x] = Dep;
    for(int i = 0;i < G[x].size();i++) {
        int y = G[x][i];
        if(y == fa) continue;
        dfs2(y,x,Dep+W[x][i]);
    }    
}
int main()
{
    n = read();m = read();
    for(int i = 1;i < n;i++) {
        LL a = read(),b = read(),c = read();sum += c;
        G[a].push_back(b);G[b].push_back(a);
        W[a].push_back(c);W[b].push_back(c);
    }
    dfs(1,0,0);dfs1(rt,0,0);dfs2(rt2,0,0);
    for(int i = 1;i <= n;i++) ans[i] = sum*2-max(dis[i],dis2[i]);
    sort(ans+1,ans+1+n);
    LL Ans = 1;
    for(;Ans <= n;Ans++){
        if(m < ans[Ans]) break;
        m -= ans[Ans];
    }  
    cout << Ans-1 << endl;
    return 0;
}