建立第二条边$(u,v)$后，会形成新的环
若两环不重合，则$(u,v)$间的路径只需走一次，答案更优
若两环重合，还需将第二个环与建立新的道路相结合，重合部分由只需走一次变成不得不走两次
所以
$k=1$时，两遍$dfs$求树的直径，链接直径($L1$)的两端，答案为$2*(n-1)-L1+1$
$k=2$时，把直径($L1$)上的边权取反，再求一遍直径($L2$)，答案即为$2*n-L1-L2$
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define ll long long 5 const int mod=1e5+3; 6 const int maxn=1e5+10; 7 inline int read(){ 8 int x=0,f=1; 9 char c=getchar(); 10 while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} 11 while(c>=‘0‘&&c<=‘9‘){x=(x*10)+c-‘0‘;c=getchar();} 12 return x*f; 13 } 14 int n,k,d[maxn],fa[maxn];bool vis[maxn]; 15 struct edge{ 16 int nxt,to,w; 17 }e[maxn<<1]; 18 int head[maxn],cnt=1,ans; 19 inline void add(int from,int to,int w){ 20 e[++cnt].to=to;e[cnt].nxt=head[from]; 21 e[cnt].w=w;head[from]=cnt; 22 } 23 void dfs(int x,int &rt){ 24 vis[x]=1; 25 for(int i=head[x];i;i=e[i].nxt){ 26 if(vis[e[i].to])continue; 27 d[e[i].to]=d[x]+1; 28 if(d[e[i].to]>=d[rt])rt=e[i].to; 29 fa[e[i].to]=i;dfs(e[i].to,rt); 30 } 31 vis[x]=0; 32 } 33 void dp(int x,int &root){ 34 vis[x]=1; 35 for(int i=head[x];i;i=e[i].nxt){ 36 if(vis[e[i].to])continue; 37 dp(e[i].to,root); 38 root=max(root,d[x]+d[e[i].to]+e[i].w); 39 d[x]=max(d[x],d[e[i].to]+e[i].w); 40 } 41 } 42 int main(){ 43 n=read();k=read(); 44 for(int i=1;i<n;i++){ 45 int u,v; 46 u=read();v=read(); 47 add(u,v,1);add(v,u,1); 48 } 49 int rt=1; 50 dfs(1,rt); 51 d[rt]=fa[rt]=0; 52 int root=rt; 53 dfs(rt,root); 54 ans=((n-1)<<1)-d[root]+1; 55 if(k==2){ 56 while(fa[root]){ 57 e[fa[root]].w=-1;e[fa[root]^1].w=-1; 58 root=e[fa[root]^1].to; 59 } 60 root=0; 61 memset(d,0,sizeof(d)); 62 dp(rt,root); 63 ans-=root-1; 64 } 65 printf("%d",ans); 66 return 0; 67 } 68 } 69 signed main(){ 70 gengyf::main(); 71 return 0; 72 }