「APIO2010」巡逻题解

阅读原文时间：2023年07月09日阅读：3

来源 LCA

个人评价：lca求路径，让我发现了自己不会算树的直径（但是本人似乎没有用lca求）

「APIO2010」巡逻

大意：有一个有n个节点的树，每条边权为1，一每天要从1号点开始，遍历所有的边，再回到1号点，每条道路都经过两次，为了减少需要走的距离，可以增加K\((1\leq K\leq 2)\)条新的边（可以自环），且每天必须经过这K条边正好一次，请计算最佳方案是总路程最小，并输出最小值

因为K很小，所以我们可以试着手推一下每种情况

2.1 不加边

从1号点出发，要把每个边遍历一遍再回到1号点，会恰好经过每条边2次，经过的路线总长为2(n-1)。

2.2 加1条边

因为这是一棵树，我们加一条边就会使它变成环，这个环便可以在遍历图的时候减少重复遍历的长度

如：

观察可以发现，在2和8之间加一条边后，2~8的路径经过的次数就会减一，加上新的这条边的边权，所以对应的，总的需要经过的路径总长度也会改变

那么也能很显然的看出，我们要尽量选择隔得远的两个节点建边，可以使得节省的路径更长

换个说法：找到树上距离最长的两点

于是，是不是想到了什么？

对，树的直径

那这样我们就可以用树的直径来求出两个距离最长节点，在他们之间建一条边，然后用lca算出他们的路径长度dist1，答案就应该是\(2(n-1)-dist1+1\)

那么这样，我们也就拿到了30分

2.3 加两条边

第一条边加完了，再各种手推的加第二条边的情况

2.3.1 两个环有重叠

两环重叠部分1-3-5-8，长度为3；车子还要跑正好一遍1-8这条新路，就导致1-3-5-8要多走一遍，多增加了4的长度

肯定不行！

所以我们要让它的重叠部分长度为0（不然还不如自环）！

2.3.2 两个环无重叠

那就没有多跑的影响，如：

2.3.3 如何计算

那应该怎么计算多在哪里建一条边呢？

经过我们之前的推导，肯定也是在直径上，但是我们这里要不让它有重叠，也就是说，直径上的路径不应该有之前第一次直径的路径，所以就可以考虑把之前直径的路径的边权变为-1，在跑一次直径就ok了,长度记为dist2

那么答案就应该是\(2(n-1)-dist1-dist2+2\)

2.4 时间复杂度

第一次直径O(n),修改边权O(n),第二次直径O(n)

噢，O(n)的整体算法！

3.0 树的直径

考虑到我一开始都忘了这个知识点，还是简单补充一下吧

这道题的一个最直观的考点——树的直径

树的直径简单来说就是树中最长的链，下面将有两种O(n)的方法来求树的直径。

背景：假设树以N个节点N-1条边以无向图的形式给出并以邻接表的形式给出。

第一种：树形DP求树的直径

我们用dis[x]表示x节点到叶子节点的最大值（单方面往下）

看不懂转移的可以自己推一下很显然

代码实现：

void dp(int x){
    vis[x]=1;
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v])continue;
        dp(v);
        ans=max(ans,dis[x]+dis[v]+e[i].w);
        dis[x]=max(dis[x],dis[v]+e[i].w);
    }
}

优点：可以处理负权值的问题（就比如我们这里的第二条直径）

但是缺点就是不好记录直径的起始点和终结点和路径（也可能是我太逊

第二种：两次dfs(bfs)求直径

方法：先从任意一点P出发，找离它最远的点Q，再从点Q出发，找离它最远的点W，W到Q的距离就是是的直径

（我不想写证明！）

证明：

代码：

void dfs(int x,int fa){
    if(dist[x]>maxx){
        maxx=dist[x];
        st=x;
    }
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(v!=fa){
            dist[v]=dist[x]+e[i].w;
            dfs(v,x);
        }
    }
}
.....一堆代码
int main(){
    ...
    dfs(1,0);
    S=st;
    maxx=0;
    dist[st]=0;
    dfs(st,0);
    T=st;
    .....
}//S，T就是直径的两个端点

优点：很容易记录直径的两个端点和路径

缺点：无法处理负边权

3.1定义

struct node{
    int to,nxt,w;
}e[200100];//存边结构体
int cnt,head[100100]；//存边需要
int dist[100100];//dp需要,表示x节点到叶子节点的最大值
int l2;//第二条直径的长度
int l1；//记录dfs找直径时的直径长度
int FA[100100];//在更新边权的时候需要直接跳fa，这里面保存的是以直径的其中一个端点为根的情况下的fa情况
int vis[100100];//dp需要

3.2 输入

scanf("%d%d",&n,&k);
for(int i=1;i<n;i++){
    int x,y;
    scanf("%d%d",&x,&y);
    add(x,y);//建双向边
    add(y,x);//因为后面会修改边权，所以add直接把初始边权变为1
}

3.3 计算

3.3.1 求第一条直径

void dfs(int x,int fa){//第一次直径
    FA[x]=fa;//因为会跑两边dfs，所以保存的是第二次的（真正直径）
    if(dist[x]>maxx){//如果x到根的距离比最大值大，更新
        l1=dist[x];
        st=x;//记录节点
    }
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(v!=fa){
            dist[v]=dist[x]+e[i].w;//更新到根节点的距离
            dfs(v,x);
        }
    }
}

这里面第二次计算后l1的值就是直径的长度，当然知道了两个节点你也可以用lca求（有什么必要呢）

3.3.2 修改边权

因为第二次dfs完后的根节点就是第一条直径其中的一个端点，所以直径一定是另一个端点到根节点的路径

void dfs1(int x,int fa){//更新边权
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa){//如果这条边是连接它和它父亲
            //记得改双向边！！！！！！
            e[i].w=-1;
            e[i+1].w=-1;
            dfs1(v,FA[v]);//继续找父亲的父亲~··
        }
    }
}

注意：这里是需要把两条边都修改为-1，我在这里wa了好久！

3.3.3 求第二条直径的长度

我一开始一直在搞两个dfs的方法，后面静态调试才发现不对（再次声明两次dfs的方法不可以处理负边权！！）

树形dp就好了，这个可以处理负边权

void Dp(int x){
    vis[x]=1;
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v])continue;
        Dp(v);
        l2=max(l2,dist[x]+dist[v]+e[i].w);//更新"直径"长度
        dist[x]=max(dist[x],dist[v]+e[i].w);//更新dist的值
    }
}
//最后l2就是第二条直径的长度了

3.4 输出

if(k==1){//判断一下输出就好了
    printf("%d",(n-1)*2-l1+1);
}else{
    printf("%d",n*2-l1-l2);
}

3.5 总体代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
struct node{
    int to,nxt,w;
}e[200100];
int cnt,head[100100],dist[100100],l2;
void add(int u,int v){//建边
    cnt++;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].w=1;//手动增加边权以便后面好处理
}
int l1,st,FA[100100],vis[100100];
void dfs(int x,int fa){//第一次直径
    FA[x]=fa;
    if(dist[x]>l1){
        l1=dist[x];//记录直径长度
        st=x;//节点
    }
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(v!=fa){
            dist[v]=dist[x]+e[i].w;//更新长度
            dfs(v,x);
        }
    }
}
void dfs1(int x,int fa){//更新边权
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa){
            e[i].w=-1;//更新双向边边权
            e[i+1].w=-1;
            dfs1(v,FA[v]);
        }
    }
}
void Dp(int x){
    vis[x]=1;
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v])continue;
        Dp(v);
        l2=max(l2,dist[x]+dist[v]+e[i].w);//更新第二条直径
        dist[x]=max(dist[x],dist[v]+e[i].w);//更新dist
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);//加边
        add(y,x);
    }
    dfs(1,0);
    int S=st;//记录一个节点
    l1=0;
    dist[st]=0;
    dfs(st,0);
    int T=st;//记录另一个节点
    memset(dist,0,sizeof(dist));
    memset(vis,0,sizeof(vis));
    dfs1(T,FA[T]);//更新边权，是以S为根，到T的路径
    Dp(1);//第二次求直径
    if(k==2){
        printf("%d",(n-1)*2-l1-l2+2);
    }else{
        printf("%d",(n-1)*2-l1+1);
    }
    return 0;
}