传送门 k=0显然每条边都要走两次，答案=(n-1)*2 k=1我们找到树上最长链，在两段连边 在环上的就不用再走一遍了 答案=(n-1)-链长+1 k=2在k=1的基础上将那些边编圈变为-1，再跑最长链 不再环上显然只要一遍 但是在两个环上要走两遍。 答案=(n-1)-链长1+1-链长2+1
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #define ll long long #define N 100005 using namespace std; struct edge{ int from,to,value,next; }e[N*2]; int head[N],son1[N],son2[N]; int n,k,x,y,u,ans,sum,tot; inline int read(){ int k=0; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()); for (;ch>='0'&&ch<='9';ch=getchar()) k=k*10+ch-48; return k; } inline void ins(int x,int y,int u){ e[++tot].from=x; e[tot].to=y; e[tot].value=u; e[tot].next=head[x]; head[x]=tot; } int dfs(int x,int fa){ int ma1=0,ma2=0,now; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa){ now=dfs(e[i].to,x)+e[i].value; if (now>ma1){ ma2=ma1; son2[x]=son1[x]; ma1=now; son1[x]=i; } else if (now>ma2){ ma2=now; son2[x]=i; } } if (ma1+ma2>sum){ sum=ma1+ma2; u=x; } return ma1; } int main(){ n=read(); k=read(); for (int i=1;i<n;i++){ x=read(); y=read(); ins(x,y,1); ins(y,x,1); } ans=(n-1)*2; sum=u=0; dfs(1,-1); ans-=sum-1; if (k==2){ for (int i=son1[u];i;i=son1[e[i].to]) e[i].value=e[i+1].value=-1; for (int i=son2[u];i;i=son1[e[i].to]) e[i].value=e[i+1].value=-1; memset(son1,0,sizeof(son1)); memset(son2,0,sizeof(son2)); sum=u=0; dfs(1,-1); ans-=sum-1; } printf("%d",ans); }