[APIO2010]巡逻(树的直径+再次直径)

题面

楼主回归了（这段时间去颓文化课了

题目的意思是让你在一棵树上加K条边，再从1出发经过所有节点和所有边（点和边均可重复）回到1的最短路径

鉴于K == 1 || K == 2，分类讨论就好了

K = 1

不加边的时候ans = edges_sum * 2

加一条边能将ans减少这条边两点之间原来的距离-1

显然找直径是最合适的。。

所以ans = edges_sum * 2 - diameter + 1

K = 2

在K == 1的时候形成的基环树在加一条边，则红色部分要走两遍，所以ans又减少了绿色部分的长度-红色部分的长度-1

求绿色部分的长度-红色部分的长度的最大值有一种很好的方法

——把红色部分（其实是环上的部分）的边权全都变成-1（撒花花

再次跑直径

---

如果你现在跑去写代码，那么恭喜你有50%的几率像我一样DeBuG好久

因为含有负权边的直径不能用两个dfs/bfs求(第二个样例就是这样)，所以得写树形dp求直径嗯就是这样

贴上代码；

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
#define INF 0x3f3f3f3f

using namespace std;

struct Node{
	int to, nxt, len;
}e[N << 1];

int dep, lst[N], cnt, d[N], v[N], x[N], y[N], n, K, tot, dx[N];

inline void add(int u, int v) {
	e[++cnt].to = v;
	e[cnt].nxt = lst[u];
	lst[u] = cnt;
	e[cnt].len = 1;
}

inline void dfs(int x, int fa, int dep) {
	d[x] = dep;
	for (int i = lst[x]; i; i = e[i].nxt) {
		int son = e[i].to;
		if (son == fa) continue;
		dfs(son, x, dep + e[i].len);
	}
}

inline int dfs1(int x, int fa, int goal) {
	if (x == goal) return 1;
	for (int i = lst[x]; i; i = e[i].nxt) {
		int son = e[i].to;
		if (son == fa) continue;
		if (dfs1(son, x, goal)) {
			e[i].len = -1;
			return 1;
		}
	}
	return 0;
}

inline void make(int x, int fa) {
	for (int i = lst[x]; i; i = e[i].nxt) {
		int son = e[i].to;
		if (son == fa) continue;
		make(son, x);
		tot = max(tot, dx[x] + dx[son] + e[i].len);
		dx[x] = max(dx[x], dx[son] + e[i].len);
	}
}

int main() {
	scanf("%d%d", &n, &K);
	for (int i = 1; i < n; ++i) {
		scanf("%d%d", &x[i], &y[i]);
		add(x[i], y[i]);
		add(y[i], x[i]);
	}
	int ans = n - 1 << 1;
	int dmax = 0, imax = 0;
	dfs(1, 1, 0);
	for (int i = 1; i <= n; ++i) {
		if (d[i] > dmax) {
			dmax = d[i];
			imax = i;
		}
	}
	memset(d, 0, sizeof d);
	dfs(imax, imax, 0);
	dmax = 0;
	int iimax = 0;
	for (int i = 1; i <= n; ++i) {
		if (d[i] > dmax) {
			dmax = d[i];
			iimax = i;
		}
	}
	ans -= dmax - 1;
	if (K == 1) {
		printf("%d\n", ans);
		return 0;
	}
	dfs1(imax, imax, iimax);
	dfs1(iimax, iimax, imax);//正反两次把环上的所有边搞成-1
	make(1, 1);
	ans -= tot - 1;
	printf("%d\n", ans);
	return 0;
}