对于K=2的情况
我的方法是 第一次找出树的直径的路径
然后沿着树的直径上的点,对以这个点为根形成的树再求直径,看第二条路修在那颗树上会更好
#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;
}
}
int wow=0;
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-wow<<endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt=1;
//cin >> tt;
while(tt--) solve();
}