洛谷 P3629 [APIO2010]巡逻 题解【树的直径】【树形DP】【贪心】

点击量：239

   这个题真的只考树的直径啊。。。

目录

题目描述

在一个地区中有n个村庄，编号为1, 2, …, n。有n–1条道路连接着这些村 庄，每条道路刚好连接两个村庄，从任何一个村庄，都可以通过这些道路到达其 他任一个村庄。每条道路的长度均为1个单位。 为保证该地区的安全，巡警车每天要到所有的道路上巡逻。警察局设在编号为1的村庄里，每天巡警车总是从警察局出发，最终又回到警察局。下图表示一个有8个村庄的地区，其中村庄用圆表示（其中村庄1用黑色的圆表示），道路是连接这些圆的线段。为了遍历所有的道路，巡警车需要走的距离为14个单位，每条道路都需要经过两次。

为了减少总的巡逻距离，该地区准备在这些村庄之间建立 K 条新的道路， 每条新道路可以连接任意两个村庄。两条新道路可以在同一个村庄会合或结束 （见下面的图例（c））。 一条新道路甚至可以是一个环，即，其两端连接到同一 个村庄。 由于资金有限，K 只能是 1 或 2。同时，为了不浪费资金，每天巡警车必须 经过新建的道路正好一次。 下图给出了一些建立新道路的例子：

在(a)中，新建了一条道路，总的距离是 11。在(b)中，新建了两条道路，总 的巡逻距离是 10。在(c)中，新建了两条道路，但由于巡警车要经过每条新道路 正好一次，总的距离变为了 15。 试编写一个程序，读取村庄间道路的信息和需要新建的道路数，计算出最佳 的新建道路的方案使得总的巡逻距离最小，并输出这个最小的巡逻距离。

输入输出格式

输入格式：

第一行包含两个整数 n, K(1≤K≤2)。接下来n–1行，每行两个整数a,b， 表示村庄 a 与 b 之间有一条道路(1 ≤ a, b ≤ n)。

输出格式：

输出一个整数，表示新建了K条道路后能达到的最小巡逻距离。

输入输出样例

输入样例#1：

8 1

1 2

3 1

3 4

5 3

7 5

8 5

5 6

 

输出样例#1：

11

 

输入样例#2：

8 2

1 2

3 1

3 4

5 3

7 5

8 5
5 6

 

输出样例#2：

10

 

输入样例#3：

5 2

1 2

2 3

3 4

4 5

 

输出样例#3：

6

 

说明

10%的数据中，n≤1000, K=1；

30%的数据中，K=1；

80%的数据中，每个村庄相邻的村庄数不超过 25；

90%的数据中，每个村庄相邻的村庄数不超过 150；

100%的数据中，3≤n≤100,000, 1≤K≤2。

   我们如果要把每条道路都走一遍，根据树的性质，一定是每条边走2遍（隐含条件：回到1号点）。那么我们如果新建一条边，就会成环，如果链的长度为L，那么原来链上需要走的距离是L×2，现在变成了L+1，也就是只需要L+1次就可以把这个环走完并回到环的起点，所节省的距离为$ 2L-(L+1)=L-1$，随L，也就随链或环的大小单调递增。那么我们要使原来的链最长，就是树的直径。求树的直径有两种方法：两次dfs和树形DP。这道题方便起见，我两种都用到了。

   首先当k=1时，求出直径，用所有边的2倍减去直径的长度再减1（意味着新加的一条边），就是答案。而当k=2时，我们要对这张图稍作处理。

   首先根据贪心，我们需要做上一步的操作。对于下一步，我们要继续找树的直径。但是此时已经有一条链是被选入环里了，我的第一想法是把环缩掉，因为环不能对答案有贡献了，把环缩成一个点，这样就能找到新的直径，重复一开始的过程。但是这样是错的，因为环虽然不能对答案有正的贡献，但是会有负的。我们如果不管原来的环，只管没有缩掉的枝节，就会出现这种情况：

   如上是一个树的一部分，黄色部分是已经找出来的环。那么我们把它缩点成右边图的形式，缩点前后实际上是有区别的。

   左边原图的实际路程是3，而右侧只有2。而当k=1时，左边这条路径是5步，右边路径是4步。我们如果把这一段当成环，在右边的贡献是1（4-2[双向变单向]+1[新建的边]=3）。但看左边的图，中间一部分就重复走过了，贡献只有0（5-2[双向变单向]+1[单向变双向]+1[新建的边]=5）因此这种做法是错的。

   通过研究这种错误的做法，发现环不能缩，而环上边的贡献是-1，我们就可以把原来直径上的边权（注意双向）改成-1，把这点负贡献归为直径长度的贡献，再做一遍第一步就可以了。

   不过此时树上有负权边，两次DFS是个贪心（像dijkstra），不能处理负权边，我们要用树形DP求解；简单介绍一下树形DP方法：

对于每个点，找出最长链，最长链最多包含2个孩子，所以我们要存已经找到的孩子的状态去更新正在找的孩子的状态。也就是把当前状态先更新，再拿去更新其他状态（有点像容量为2的01背包？）具体可以看代码片段：

Dfs(p->n);
mx=mx>f[x]+f[p->n]+p->v?mx:f[x]+f[p->n]+p->v;//先更新答案
f[x]=f[x]>f[p->n]+p->v?f[x]:f[p->n]+p->v;//再更新当前最优链

   对于第一次找树的直径，并更新树的直径上的边权，用两次dfs做是最好的，因为没有负权，并且容易存储路径，也简单好写。

Code：

#include<cstdio>
struct node
{
    int n,v;
    node *nxt,*op;
    node(int n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=NULL;
        op=NULL;
    }
    node()
    {
        nxt=NULL;
        op=NULL;
    }
};
node head[100100],*tail[100100];
int d1,d2,L=0,l,flag=0;
int Pre[100100];
node *pre[100100];
void dfs(int x)
{
    if(l>L)
    {
        L=l;
        if(flag==0)
            d1=x;
        else
            d2=x;
    }
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(p->n==Pre[x])
            continue;
        Pre[p->n]=x;
        pre[p->n]=p;
        l+=p->v;
        dfs(p->n);
        l-=p->v;
    }
}
int f[100100];
int mx=0;
void Dfs(int x)
{
    node *p=&head[x];
    f[x]=0;
    int son=0;
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(p->n==Pre[x])
            continue;
        Pre[p->n]=x;
        Dfs(p->n);
        mx=mx>f[x]+f[p->n]+p->v?mx:f[x]+f[p->n]+p->v;
        f[x]=f[x]>f[p->n]+p->v?f[x]:f[p->n]+p->v;
    }
}
int main()
{
    int n,k,u,v;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        tail[i]=&head[i];
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        tail[u]->nxt=new node(v,1);
        tail[u]=tail[u]->nxt;
        tail[v]->nxt=new node(u,1);
        tail[v]=tail[v]->nxt;
        tail[u]->op=tail[v];//双向边都要修改
        tail[v]->op=tail[u];
    }
    l=0;
    Pre[1]=1;//求路径用的
    dfs(1);//求直径的一个端点
    flag=1;
    L--;
    l=0;
    Pre[d1]=d1;
    dfs(d1);//求完整直径
    flag=0;
    int t=d2;
    while(t!=d1)
    {
        pre[t]->v=-1;
        pre[t]->op->v=-1;
        t=Pre[t];
    }
    int ans=2*(n-1)-(L-1);//现在所要走的路程
    if(k==1)
    {
        printf("%d\n",ans);
        return 0;
    }
    Pre[1]=1;
    Dfs(1);//找新的直径
    ans-=mx-1;
    printf("%d\n",ans);
    return 0;
}