洛谷：P3629 [APIO2010]巡逻 （树形dp，思维）

思维）"/>

洛谷：P3629 [APIO2010]巡逻 （树形dp，思维）

巡逻！

题意：

• 给定一颗树，每次从 1 号结点要求走遍这颗树的所有边（至少一次），最后回到 1 号点，显然走的过程中有些边会走重复。

• 让你在这棵树上加 1 或 2 条边（连接两个存在的结点），问怎么加可以使得走的过程中尽可能少地经过边，求出这个最少的边数。

思路：

• 分情况讨论，在不加边的情况下，显然我们会把每条边走两遍（要回到 1 点），走的边数是固定的。

• 在加 1 条边的情况下，画图观察可以发现，这颗树上必定会形成一个环，经过这个环可以不走 回 这条边两点原本的路径，这也就是我们省略的边数。

• 贪心地想，要少走尽可能多的边，那这个环就要尽可能大，所以我们直接挑树的 直径 作为环。视每条边长度为 1，有一点贡献，然后求树的直径即可。（省略的边数即：直径长度 - 1，因为加的边也要走）

• 加 2 条边的情况就比较麻烦了。会发现加这条边有可能影响加第 1 条边的情况，彼此之间有重叠影响。

• 这里就使用了一个优秀的思想，在求加第 1 条边时，每条边可以给与 1 点 贡献在答案中（使其减少），加完后我们就可以把环上的边的贡献视为 -1 ！因为已经被使用过了，寓意加 第 2 条边的时候不仅没有贡献，反而会使原本的贡献消失（画图理解）

• 所以我们相当于在这颗直径上的边被标记成 -1 其他边标记成 1 的树上，再求一次 “直径”，这次最长的 “直径” 就可以当成我们的第二次贡献了。最后 总 边 数 ∗ 2 − ∑ 两 次 贡 献 总边数*2 - ∑两次贡献 总边数∗2−∑两次贡献 加在一起就是我们的答案了（注意我们边是必须加的，有可能最小巡逻距离比一开始不加边还大）

• eg：求树的直径有两种方法，{通过树的性质求解——bfs} 或 {树形dp——dfs}，bfs可以尽可能维护直径的信息，但bfs是没法求存在负权的树的直径的！此题不仅涉及求负权树直径，还涉及修改直径上的边权，所以两种用法都考察了，好题！

C o d e : Code: Code:

#include<bits/stdc++.h>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define forr(a,b,c) for(int a=b;a<=c;++a)
#define rfor(a,b,c) for(int a=b;a>=c;--a)
#define forg(a,b) for (int a = h[b]; ~a; a = ne[a])
#define all(a) a.begin(),a.end()
#define oper(a) (operator<(const a& ee)const)
#define endl "\n"
using namespace std;typedef long long ll;
typedef pair<int, int> PII;double DNF = 1e17;
const int N = 100010, M = 200010, MM = 110;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int INF = 0x3f3f3f3f, mod = 1e9 + 7;
int n, m, k, T, S, D, K;
int h[N], e[M], ne[M], w[M], idx;
int d1[N], d2[N], len2;void add(int a, int b, int x) {e[idx] = b, ne[idx] = h[a], w[idx] = x, h[a] = idx++;
}//说是bfs，因为树的独特性，也能用dfs模拟
void dfs_bfs(int x, int fa, int d[]) {forg(i, x) {int j = e[i];if (j == fa)continue;d[j] = d[x] + 1;dfs_bfs(j, x, d);}
}void dfs_change(int x) { //修改直径上的边权forg(i, x) {int j = e[i];if (d2[x] - 1 == d2[j]) { //要反过来从叶子找到根，不然会找错w[i] = w[i ^ 1] = -1;dfs_change(j);}}
}int dfs_dp(int x, int fa) { //树形dp求直径int d1, d2;d1 = d2 = 0;forg(i, x) {int j = e[i];if (j == fa)continue;int t = dfs_dp(j, x) + w[i];if (d1 < t)d2 = d1, d1 = t;else if (d2 < t)d2 = t;}len2 = max(len2, d1 + d2);return d1;
}void solve() {cin >> n >> k;mem(h, -1);forr(i, 2, n) {int a, b;cin >> a >> b;add(a, b, 1), add(b, a, 1);}//bfs求直径int p1 = 1, p2 = 1;dfs_bfs(1, -1, d1);forr(i, 1, n)if (d1[i] > d1[p2])p2 = i;dfs_bfs(p2, -1, d2);forr(i, 1, n)if (d2[i] > d2[p1])p1 = i;d1[p1] = 0;dfs_bfs(p1, -1, d1);int len1 = d1[p2];if (k == 1) {cout << 2 * (n - 1) - (len1 - 1) << endl;}else {dfs_change(p1);dfs_dp(1, -1);cout << 2 * (n - 1) - (len1 - 1) - (len2 - 1) << endl;}
}int main() {cinios;T = 1;while (T--)solve();return 0;
}
/*
*/