P3629 [APIO2010] 巡逻
大意
给定一棵有 \(n\) 个节点的树，巡警车从 \(1\) 号节点出发遍历所有边后返回，每条边需经过两次，总距离为 \(2*(n-1)\)。现可新建 \(K\) 条边\((k = \{ 1, 2\})\)，要求新建的每条边必须恰好经过一次，求规划新建边的方案，使得巡警车的总巡逻距离最小，并输出该最小值。
思路
我们可以发现，对于 \(k = 1\) 的情况，显然你求出一条直径，再把直径的两个端点连上，这样是最优的。
但是当 \(k = 2\) 的时候，我们需要再连一次，但是这样的话，我们最好选比较长的，最初的想法是选次长的直径，但是我们想想，如果你选的这条新的直径，和原来的直径，有很多重合的点，那么就不是很优，我们为了处理这个重复的玩意，其实可以把原直径的所有边赋为 \(-1\)，这样的话，我们再找最长的直径，就不会出问题了。
但是这样需要知道一个问题， dfs 求直径是无法解决边权为负的情况，于是我们考虑树形 dp 的方式，直接再记一次直径的长度即可。
设两次的直径长度为 \(L_1, L_2\)，则最终答案为：
\(k = 1\) 时：\(2 * (n - 1) - L_1 + 1\)
\(k = 2\) 时：\(2 * (n - 1) - (L_1 - 1) - (L_2 - 1)\)
代码
#include<iostream>
#include<cstring>
using namespace std;const int MAXN = 1e5 + 5;struct node{int to, nxt, len;
}e[MAXN * 2];int tot = 0, h[MAXN];
int d[MAXN];
bool vis[MAXN];void add(int x, int y, int len){e[++ tot] = {y, h[x], len};h[x] = tot;
}int n, k, d1 = 1, d2 = 0, d3 = 1, d4 = 0;
int f[MAXN];
int dp[MAXN], maxx;void dfs(int u, int fa){dp[u] = 0;for(int i = h[u]; i; i = e[i].nxt){int v = e[i].to;if(v == fa) continue;e[i].len = (vis[u] && vis[v]) ? -1 : 1;dfs(v, u);maxx = max(maxx, dp[u] + dp[v] + e[i].len);dp[u] = max(dp[u], dp[v] + e[i].len);}
}void dfs1(int u, int fa){for(int i = h[u];i;i = e[i].nxt){int v = e[i].to;if(v == fa) continue;d[v] = d[u] + e[i].len;if(d[v] > d[d1]){d1 = v;}dfs1(v, u);}
}void dfs2(int u, int fa){f[u] = fa;for(int i = h[u];i;i = e[i].nxt){int v = e[i].to;if(v == fa) continue;d[v] = d[u] + e[i].len;if(d[v] > d[d2]){d2 = v;}dfs2(v, u);}
}int main(){cin >> n >> k;for(int i = 1;i < n;i ++){int a, b; cin >> a >> b;add(a, b, 1), add(b, a, 1);}dfs1(1, 0);memset(d, 0, sizeof(d));dfs2(d1, 0);int l1 = d[d2];if(k == 1){cout << 2 * (n - 1) - l1 + 1 << '\n';return 0;}memset(vis, 0, sizeof(vis));int tmp = d2;while(tmp != 0){vis[tmp] = true;tmp = f[tmp];}maxx = 0;dfs(1, 0);int l2 = maxx;cout << 2 * (n - 1) - (l1 - 1) - (l2 - 1) << '\n';return 0;
}