APIO2010 巡逻
k==1时直接减去直径的长度
k==2时 当两个环无重叠时直接减去第一次的直径还有第二次
有重复 可以发现重复部分会走两次 将第一次直径上的边权改为-1 然后再跑一遍直径 然后\(ans=2*n-l_1-l_2\) 具体咕咕咕
注意第二次找直径不能用两次bfs或者dfs 要用树形dp 具体可以模拟一下两遍dfs时下面这个样例就知道了==
输入： 输出：
8 2 10
1 2
3 1
3 4
5 3
7 5
8 5
5 6 #include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
using namespace std;
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
const int N=1e5+50,M=30000+5,inf=0x3f3f3f3f,P=19650827;
int n,k,pre[N],ans,mxl=0,s,t;
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
int head[N],tot=1;
struct edge{int v,w,nxt;}e[N<<1];
void add(int u,int v,int w){
e[++tot]=(edge){v,w,head[u]},head[u]=tot;
}
void dfs(int u,int ff,int len){
if(len>=mxl) mxl=len,s=u;
for(int i=head[u],v;i;i=e[i].nxt)
if((v=e[i].v)!=ff) dfs(v,u,len+e[i].w);
}
void dfs2(int u,int ff,int len){
if(len>=mxl) mxl=len,t=u;
for(int i=head[u],v;i;i=e[i].nxt)
if((v=e[i].v)!=ff) pre[v]=i,dfs2(v,u,len+e[i].w);
}
int f[N][2];
void dp(int u,int fa){
f[u][1]=0,f[u][2]=0;
for(int i=head[u],v,w;i;i=e[i].nxt){
w=e[i].w,v=e[i].v;
if(v==fa) continue;
dp(v,u);
int dis=f[v][1]+w;
if(dis>f[u][1]) f[u][2]=f[u][1],f[u][1]=dis;
else if(dis>f[u][2]) f[u][2]=dis;
mxl=Max(mxl,f[u][1]+f[u][2]);
}
}
int main(){
freopen("in2.txt","r",stdin);
//freopen("xor.out","w",stdout);
rd(n),rd(k);ans=n-1<<1;
for(int i=1,u,v;i<n;++i) rd(u),rd(v),add(u,v,1),add(v,u,1);
dfs(1,0,0);dfs2(s,0,0);
ans-=(mxl-1);
if(k==1) return printf("%d",ans),0;
int x=t;
while(x!=s){
int i=pre[x];
e[i].w=e[i^1].w=-1;
x=e[i^1].v;
}
mxl=-inf;
dp(1,0);
printf("%d",ans-(mxl-1));
return 0;
}