P3629 [APIO2010] 巡逻

· · 个人记录

题意

加 k 条边，遍历到每一条边，使警察走过的边数最少

分析

$2.$ 假如加了一条边，那么会形成一个环，而且环上的边只需要走一次，其余的边要走两次。 那么，对于 $k=1$ 的话，我们就要使环上的边尽量多，也就是说我们要找树的直径，使得树的直径在环内。 而对于 $k=2$ 的话，再加一条边的时候，会再多一个环。 这时我们可以知道： $1.$ 如果一条边仅在第二个环出现过，只用走一次。 $2.$ 如果一条边在两个环都出现过，要走两次。 $3.$ 如果一条边在两个环都没出现过，要走两次。 所以，我们只要给第一个环上的边 $-1$ 的权值，其余边给$1$ 的权值，用 $dp$ 求出树上权值最大的一条路径就行了。 最后的答案还是很好推的，请读者自行推导。 ### $code 
#include<bits/stdc++.h>
#define N 100005
#define rint int 
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}  
    return x*f;
}
int n,k,cir1,cir2,pos,ans,tot;  
int d[N],fa[N],flag[N];
int Head[N],to[N<<1],Next[N<<1];
inline void add(int u,int v){to[++tot]=v,Next[tot]=Head[u],Head[u]=tot;}
inline void dfs(int x,int f){ //dfs 求直径 
    fa[x]=f;
    if(d[pos]<d[x]) pos=x;
    for(rint i=Head[x];i;i=Next[i]){
        rint y=to[i];if(y==f) continue;
        d[y]=d[x]+1,dfs(y,x);
    }
}
inline void dp(int x,int f){ //dp 求直径 
    for(rint i=Head[x];i;i=Next[i]){
        rint y=to[i],z;if(y==f) continue;
        dp(y,x);
        if(flag[x]&&flag[y]) z=d[y]-1;  //如果是在第一个环上的边，权值 -1 
        else z=d[y]+1; //否则 +1 
        cir2=max(cir2,d[x]+z);
        d[x]=max(d[x],z);
    }
}
int main(){
    n=read(),k=read();
    for(rint i=1;i<n;++i){
        rint x=read(),y=read();
        add(x,y),add(y,x);
    }
    dfs(1,0),d[pos]=0,dfs(pos,0);cir1=d[pos]; 
    if(k==1) return printf("%d\n",((n-1)<<1)-cir1+1),0;
    memset(d,0,sizeof(d));
    while(pos) flag[pos]=1,pos=fa[pos]; //记录第一个环上的点 
    dp(1,0);  
    printf("%d\n",((n-1)<<1)-cir1-cir2+2);  
    return 0;
}