84分求调

我的方法是 第一次将树的直径的路径求出来

对于第二条路，沿着树的直径的路径，对路径上的点为根形成的树，再求直径，看把第二条路放在哪里更省距离

sheng = max(sheng,js*2-(1+d+(js-d)*2));

这个语句就是计算对于每个树，把第二条路建在上面，能省多少，并求最大值

js是树有几个顶点

n是树的直径

#include <bits/stdc++.h>
#define int long long
//#define LL long long
#define double long double
//#define lf Lf
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define endl "\n"
#define PII pair<int,int>
#define Gheap priority_queue<int,vector<int>,greater<int>>
#define Lheap priority_queue<int>
#define MAXN 0x3f3f3f3f
#define MINN -0x3f3f3f3f
using namespace std;
const int N=1e5+100,M=2*N;
//int e[N],w[M],h[M],ne[M],idx;

unordered_map<int,vector<PII>> Edge;
unordered_map<int,int> inBody;
int dp[N],g[N][3],du[N],d,js,f[N];
int maxx,node;

void dfs(int u, int fa)
{
	dp[u]=0;
	int max1=0,max2=0;
	for (auto z : Edge[u]) 
	{
		int v=z.fi;
		int w=z.se;
		if (v == fa) continue;
		dfs(v, u);
		if(dp[v]+w>max1)
		{
			max2=max1;
			g[u][2]=g[u][w];
			max1=dp[v]+w;
			g[u][w]=v;
		}
		else if(dp[v]+w>max2)
		{
			max2=dp[v]+w;
			g[u][2]=v;
		}
		dp[u]=max(dp[v]+w,dp[u]);
	}
	if(max1+max2>maxx)
	{
		maxx=max1+max2;
		node=u;
	}
}

void sub_dfs(int u,int fa)
{
	f[u]=0;
	for (auto z : Edge[u])
	{
		int v=z.fi;
		int w=z.se;
		if (v == fa or inBody[v]==1) continue;
		js++;
		sub_dfs(v, u);
		d = max(d, f[u] + f[v] + w); 
		f[u] = max(f[u], f[v] + w); 
	} 
}

void solve()
{
    int n,k;
    cin>>n>>k;

    for(int i=1;i<=n-1;i++)
    {
    	int a,b;
    	cin>>a>>b;
    	Edge[a].pb({b,1});
    	Edge[b].pb({a,1});
    }
    maxx=MINN;
    dfs(1,0);

    vector<int> body;

    int idx=node;
    while(idx)
    {
    	body.eb(idx);
    	inBody[idx]=1;
    	idx=g[idx][1];
    }
    idx=g[node][2];
    while(idx)
    {
    	body.eb(idx);
    	inBody[idx]=1;
    	idx=g[idx][1];
    }

    int ans = body.size(),fg=0;k--;
    int sheng = 0;

    for(auto z:body)
    {
    	d=0;
    	js=0;
    	sub_dfs(z,0);
    	if(js>0)
    	{
    		fg=1;
    		sheng = max(sheng,js*2-(1+d+(js-d)*2));
    		ans+=js*2;
    	}
    }

    if(k==1)
    {
		if(fg==1) ans-=sheng;
		else ans++;
    }
    cout<<ans<<endl;

}

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--) solve();
}