[APIO2010] 巡逻
若$k=0$时，则没有走过任何一个新建道路,所以答案为$2 imes (n-1)$，因为用$dfs$可以发现每条边经过一次，回溯一次
设树的直径为$L1$
若$k=1$时，则我们发现若连接$(u,v)$,则会产生一个环，环中每条边只经过一次，其余都经过两次，则答案是$2 imes{(n-1)}-L1+1$,+1是因为要走过这条边，再直径的连边
若$k=2$时，因为我们肯定是要选当$k=1$时的情况，但是后面应该怎样去选择呢。若选边$(u1,v1)$,则有肯定又形成一个环，目前两个环，环中若两环有共边，则走两次，其余环内就走一次即可，所以就可以想到让第一次的树上直径中的每一条边$-1$，然后在找一个当前树上的直径$(L2)$，所以答案为$2 imes{(n-1)}-(L1-1)-(L2-1)$
即可求树上直径的方法:1.$dfs$,$bfs$2.$dp$（两者都写了,I think 第一种只适应都为正权的边，有负的就崩了）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read() { int f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } struct node{ int u,v,w,nex; }x[200001]; int head[200001],n,k,cnt,dis[200001]; void add(int u,int v,int w){ x[cnt].u=u,x[cnt].v=v,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++; } void dfs(int f,int fa){ for(int i=head[f];i!=-1;i=x[i].nex){ if(x[i].v==fa) continue; dis[x[i].v]=dis[f]+x[i].w; dfs(x[i].v,f); } } bool ff; void dfs1(int f,int fa,int end){ if(ff) return; if(f==end){ ff=true; return; } for(int i=head[f];i!=-1;i=x[i].nex){ if(x[i].v==fa) continue; x[i].w=-1; x[i^1].w=-1; dfs1(x[i].v,f,end); if(ff) return; x[i^1].w=1; x[i].w=1; } } int get(){ memset(dis,0,sizeof(dis)); dfs(1,0); int maxn=0,pos; for(int i=1;i<=n;i++){ if(dis[i]>maxn) maxn=dis[i],pos=i; } memset(dis,0,sizeof(dis)); int sta=pos; dfs(pos,0); maxn=0; for(int i=1;i<=n;i++){ if(dis[i]>maxn) maxn=dis[i],pos=i; } int end=pos; dfs1(sta,0,end); return maxn; } int d[200001],maxn; int dp(int f,int fath){ for(int i=head[f];i!=-1;i=x[i].nex){ if(x[i].v==fath) continue; dp(x[i].v,f); maxn=max(maxn,d[f]+d[x[i].v]+x[i].w); d[f]=max(d[f],d[x[i].v]+x[i].w); } return maxn; } int main() { memset(head,-1,sizeof(head)); n=read(),k=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); add(u,v,1),add(v,u,1); } int L1=get(); if(k==1)printf("%d ",(n-1)*2-L1+1); else{ int L2=dp(1,0); printf("%d ",n*2-L1-L2); } }