[APIO2010]巡逻

洛咕

BZOJ

题意:给定一棵n个点边权为1的树,允许再建立\(K(K=1,2)\)条边,求从节点1出发,遍历所有的点后,回到节点1的最小距离.

分析:嗯.蓝书上讲得挺详尽的.\(K=1\)时,答案就是\(2*(n-1)-l1\),\(l1\)表示树的直径长度.\(K=2\)时,答案就是\(2*(n-1)-l1-l2\),\(l2\)表示将\(l1\)上的所有边权取反后的新直径.

很诡异的是,第一次求直径的时候因为要记录直径上的路径(为了把边权取反)所以要用两次\(DFS/BFS\)求直径法.第二次求直径的时候因为树上有负权,所以只能用\(dp\)法.两次都限制了求直径的方法.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=2e5+5;
int a[N],b[N];
int n,k,l1,l2,dis[N],pre[N];
int tot,head[N],nxt[N],to[N],w[N];
inline void add(int a,int b,int c){
    nxt[++tot]=head[a];head[a]=tot;
    to[tot]=b;w[tot]=c;
}
inline void dfs1(int u,int fa){
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(v==fa)continue;
        dis[v]=dis[u]+w[i];dfs1(v,u);
    }
}
inline void dfs2(int u,int fa){
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(v==fa)continue;
        dis[v]=dis[u]+w[i];pre[v]=u;dfs2(v,u);
    }
}
map<int,int>Map;
inline void dp(int u,int fa){
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(v==fa)continue;
        dp(v,u);
        l2=max(l2,dis[u]+dis[v]+w[i]);
        dis[u]=max(dis[u],dis[v]+w[i]);
    }
}
int main(){
    n=read();k=read();
    for(int i=1;i<n;++i){
        a[i]=read();b[i]=read();
        add(a[i],b[i],1);add(b[i],a[i],1);
    }
    dfs1(1,0);
    int maxn=0,pos1,pos2;
    for(int i=1;i<=n;++i)if(dis[i]>maxn)maxn=dis[i],pos1=i;
    memset(dis,0,sizeof(dis));dfs2(pos1,0);
    maxn=0;for(int i=1;i<=n;++i)if(dis[i]>maxn)maxn=dis[i],pos2=i;
    tot=0;memset(head,0,sizeof(head));
    while(pos2!=pos1){
        add(pre[pos2],pos2,-1);add(pos2,pre[pos2],-1);
        Map[pos2]=pre[pos2];pos2=pre[pos2];++l1;
    }
    if(k==1){
        printf("%d\n",2*(n-1)-(l1-1));
        return 0;
    }
    for(int i=1;i<n;++i){
        if(Map[a[i]]!=b[i]&&Map[b[i]]!=a[i]){
            add(a[i],b[i],1);add(b[i],a[i],1);
        }
    }
    memset(dis,0,sizeof(dis));
    dp(1,0);
    printf("%d\n",2*n-l1-l2);
    return 0;
}

[APIO2010]巡逻

原文：https://www.cnblogs.com/PPXppx/p/11563894.html