「Bzoj 1912」「Apio2010」巡逻 (树的直径,负权直径)

BZOJ 1912
题意:给你一棵$n$点$n-1$边的树,要从$1$开始出发走遍所有边然后回到$1$,现在你可以加$K(1 \leq K \leq 2)$条边,并且加的边正好走一次,求出最小的路程。

明显如果不加边答案即为$2(n-1)$。
考虑加一条边情况:此时加一条边在$(x,y)$之间,相当于使答案少了$dis(x,y)-1$。即只走这条边不用回溯$x,y$之间的边。我们想要答案最小,那么$dis(x,y)$要最大,所以$x,y$是直径的两个端点。

加两条边的情况,可以考虑先将直径加边,然后再将直径上的边删除,然后树变为森林,求每棵树的直径取最大值。但不一定第一条边加在直径最优,这个贪心是错的,但是分还挺多。
我们考虑第一条边还是先加直径,但是我们之后将直径上的边权都改为$-1$,然后再对树求一下直径,然后答案减去直径长-1。
因为-1相当于还原之前选的直径上的边,即这个位置还是走两次。感觉和Bzoj 1050类似。
这里有负权就不能两次搜索找直径了,所以要用DP,DP有点类似点分治。
最开始原图还是最好用两次搜索,这样方便找到端点。

知识点
1、负权时不能用搜两次找直径,要用DP
2、想到的做法没有完全落实不要认为是对的,但是迫不得已可以写来骗分

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
struct edge {
int v, w, nxt;
} ed[MAXN * 2];
int n, K, en, hd[MAXN], ans;
int zj1, zj2, dis[MAXN], hh;
void ins(int u, int v, int w) {ed[++en] = (edge){v, w, hd[u]}, hd[u] = en;}
void dfs_dis(int u, int fa) {
for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != fa) {
dis[e.v] = dis[u] + e.w;
dfs_dis(e.v, u);
}
}
}
int dfs_bj(int u, int fa) {
if (u == zj2) return 1;
int fl = 0;
for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != fa) {
int gg = dfs_bj(e.v, u);
fl |= gg;
if (gg) ed[i].w = ed[i ^ 1].w = -1;
}
}
return fl;
}
void dfs_dp(int u, int fa) {
for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != fa) {
dfs_dp(e.v, u);
hh = max(hh, dis[e.v] + e.w + dis[u]);
dis[u] = max(dis[u], dis[e.v] + e.w);
}
}
}
void clean() {
en = -1, ms(hd, -1);
}
int solve() {
clean();
scanf("%d%d", &n, &K), ans = (n - 1) * 2;
for (int x, y, i = 1; i < n; ++i) {
scanf("%d%d", &x, &y);
ins(x, y, 1), ins(y, x, 1);
}
ms(dis, 0), zj1 = 0, dfs_dis(1, 0);
for (int i = 1; i <= n; ++i) if (dis[i] > dis[zj1]) zj1 = i;
ms(dis, 0), zj2 = 0, dfs_dis(zj1, 0);
for (int i = 1; i <= n; ++i) if (dis[i] > dis[zj2]) zj2 = i;
ans = ans - dis[zj2] + 1;
if (K == 1) return printf("%d\n", ans), 0;
dfs_bj(zj1, 0);
ms(dis, 0), hh = 0, dfs_dp(1, 0);
ans = ans - hh + 1;
printf("%d\n", ans);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------