前置知识须知：$DP$求直径，两次$DFS/BFS$求直径

解题思路：首先看一下在没有增边的情况遍历整棵树需要的开销，由$DFS$可以知道每个点会递归一次（先传导下来再返回上去），所以总花费就是$2 \times (n-1)$

连完边后图肯定会出现一个环，而我们也一定会选择走这个环，所以这个环所省下的花销就是连接前选择的边的总花费$L$，因为我们不用对这$L$条边重复走了，而是直接以花费$1$走新的路径

让我们先考虑$k=1$的情况，首先贪心的想一下这条路径应该连接哪两个点，很容易就想到应该连接这颗树的直径的两端点而使$L$尽可能大，如图，我们就应该连接点$2$和$8$，省下的花销就是直径的长度$L1$

那么此时的花销就是$原花销-省下的花销+走新路的花销=2 \times (n-1)-L1+1$

如果你看懂了以上内容，恭喜你已经可以暴骗写出$曼巴pts$了，接下来我们就要考虑$k=2$的情况了(写完也就能$AC$这道$luogu$水紫了)

$k=2$的情况无非就是在$k=1$的基础上在加一条边构成一个新的环，所以我们只要再找一次的直径$L2$就行了

¿吗?

对于增加路径的目的，我们无非就是想要少走一些重复的路，如果两次的直径的部分路径重叠，则我们第一次增加路径所减少的花销就会减少，简而言之，总花销会增加$L1 \cap L2$的元素数量

将这个性质抽象一下结合到图上，因为我们把答案要减去第二次直径上未重复的路径再加上重复的路径，那不就是将第一次的直径$L1$上的边的边权修改$-1$吗？$L2=1 \times 未重复边数 + -1 \times 重复边数$，减上一个数的负数就是加上它，不就满足条件了吗，答案就是$2 \times (n-1)-(L1+1)-(L2+1)=2 \times n-L1-L2$

如果你听懂了，那就恭喜你成功$(脑内)AC$了这道题目 orz orz orz

---

实现细节：这里就要回收开头了，可能有人会说$"主包主包，为神马前置知识需要两个求直径的方法都要会捏？"$，看一下我们的目的你就会知道了

在$k=1$时，我们要记录下直径的路径，所以使用两次$DFS/BFS$会方便一点（如果你硬要用$DP$导致$MLE$或者写不出来我也管不了，写出来我也没得说）

在$k=2$时，因为存在负权并且我们只需要直径的长度就行，所以我们只能用$DP$去解

（都讲到这里了，应该不会再写错了吧？）

AC代码

Details

#include<bits/stdc++.h>
using namespace std;
#define pii pair< int,int >

const int N=2e5+10;

int long_dis, point;
int pre[N], DP[N];
bool L[N], vis[N];
vector< pii > dra, rode[N];

void dfs( int p,int fa,int dis )
{
    for( auto &[x,cost]:rode[p] )
    {
        if( x == fa ) continue;
        pre[x]=p;
        dfs( x,p,dis+cost );
    }
    if( dis > long_dis )
    {
        long_dis=dis;
        point=p;
    }  
}

void dp( int p )
{
    vis[p]=true;
    for( auto &[x,cost]:rode[p] )
    {
        if( vis[x] ) continue;
        if( L[p] && L[x] ) cost=-1;
        dp( x );
        long_dis=max( long_dis,DP[p]+DP[x]+cost );  
        DP[p]=max( DP[p],DP[x]+cost );
    }
}

int main()
{
    // freopen( "txt.in","r",stdin );
    // freopen( "txt.out","w",stdout );
    ios::sync_with_stdio( false );
    cin.tie( nullptr ), cout.tie( nullptr );
    int n, k;
    cin>>n>>k;
    for( int i=1;i<n;i++ )
    {
        int a, b;
        cin>>a>>b;
        rode[a].push_back( { b,1 } ), rode[b].push_back( { a,1 } );
    }
    int L1=0, L2=1;

    dfs( 1,0,0 );
    for( int i=1;i<=n;i++ ) pre[i]=0;
    long_dis=0;
    dfs( point,0,0 );
    L1=long_dis;
    if( k == 2 )
    {
        long_dis=0;
        for( int i=point;i;i=pre[i] ) L[i]=true;
        dp( 1 );
        L2=long_dis;
        cout<<2*n-L1-L2;
        return 0;
    }
    cout<<2*( n-1 )-L1+1;
} 

时间复杂度：$O(n)$