#Z0463. 巡逻1

2024-02-07 15:12

文章标签 巡逻 z0463

本文主要是介绍#Z0463. 巡逻1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

在一个地区中有 n 个村庄，编号为 1, 2, ..., n。有 n – 1 条道路连接着这些村庄，每条道路刚好连接两个村庄，从任何一个村庄，都可以通过这些道路到达其他任一个村庄。每条道路的长度均为 1 个单位。为保证该地区的安全，巡警车每天要到所有的道路上巡逻。警察局设在编号为 1 的村庄里，每天巡警车总是从警察局出发，最终又回到警察局。

下图表示一个有 8 个村庄的地区，其中村庄用圆表示（其中村庄 1 用黑色的圆表示），道路是连接这些圆的线段。为了遍历所有的道路，巡警车需要走的距离为 14 个单位，每条道路都需要经过两次。

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

在(a)中，新建了一条道路，总的距离是 11。

试编写一个程序，读取村庄间道路的信息和需要新建的道路数，

计算出最佳的新建道路的方案使得总的巡逻距离最小，并输出这个最小的巡逻距离。

Format

Input

第一行包含两个整数 n

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

3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。

Output

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

Samples

输入数据 1

Copy

输出数据 1

思路

rt,有一棵树，要求我们在树上加上1两条边，是警察遍历时经过的路径最短，关于路径，有以下几个要求

造出来的路必须且仅经过一遍
允许出现某条路有某点连向同一个点
从一号节点出发，回到一号节点

只要不从自己连到自己(造的路必须通过)，都是可以帮警察省下路程的，所以我们不妨考虑一下贪心地选择，即选择树上距离最长的两点，因为不管我们选择了哪两个点，省下的距离都是两点之间的距离 - 1（走造的那条路还要 1） 那么我们只要找到距离最大的两个点就可以省下最长的路程这就引出了我们的主角——树的直径，不会的可以看看

求树的直径(史上最详细,匠心之作)_树的直径存在负边权-CSDN博客

然后就可以省下树的直径-1的路啦(显然这是省的最多的)，由于本来要走的路程是(n-1)*2(每条路走两次),所以答案就是

2 * (n - 1) - lzj + 1;//lzj是树的直径

代码

#include <bits/stdc++.h>
using namespace std;
int a,b,n,k,deep[1000001],zj,zjj,lzj;
vector<int> vec[1000001];
void dfs(int x,int fa,int d)
{deep[x] = d;for(int i = 0;i < vec[x].size();i++)if(vec[x][i] != fa)dfs(vec[x][i],x,d + 1);
}
void qzj()
{dfs(1,0,1);int t = 0;for(int i = 1;i <= n;i++)if(t < deep[i]){t = deep[i];zj = i;}dfs(zj,0,1);t = 0;for(int i = 1;i <= n;i++)if(t < deep[i]){t = deep[i];zjj = i;}lzj = t - 1;
}
int main()
{cin>>n;for(int i = 1;i < n;i++){cin>>a>>b;vec[a].push_back(b);vec[b].push_back(a);}qzj();cout<<2 * (n - 1) - lzj + 1;return 0;
}