APIO2010 巡逻 树形DP

说是树形DP，其实就是在树上乱搞。。。。

k=1的时候，随意啦。。。想咋做就咋做，我是用了两次bfs求出来最长链

k=2的时候，用了贪心的思想，显然如果已经加入一条最长链以后，第二条最长链有可能不是最优解。。。大概就那个意思

所以我们可以在第一次求完最长链以后，把链上的所有边权 都从1改成-1

然后dfs求一次最长路

当然最后都累加到ans里

答案就是2*(n-1)-ans+k

ps：今天上午刚刚学的c语言编程风格啊有没有感觉很帅。。。。！！！

就是空格太多了。。。。

不知道在比赛前一个星期改编程习惯会使什么结果？

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define rep (i, j, k) for (int i = j; i <= k; i++)
#define MAX 100010

using namespace std;

int to[MAX * 2], next[MAX * 2], head[MAX], value[MAX * 2], n, k, done[MAX], d[MAX];
int num = 1, ans = 0;
int f[MAX], tool, Max = 0;

inline void add (int from, int To, int Value)
{
	to[++num]=To;
	next[num]=head[from];
	head[from]=num;
	value[num]=Value;
}

inline int bfs(int x)
{
	int Max = -0x7fffffff, p;
	memset (done, 0, sizeof(done));
	queue <int> q;
	q.push (x);
	done[x] = 1;
	d[x] = 0;
	int now;
	while (!q.empty())
	{
		now = q.front();
		if (d[now] > Max && now != x)
			Max = d[now], p = now;
		q.pop();
		for (int i = head[now]; i; i=next[i])
			if (!done[to[i]])
				d[to[i]] = d[now] + value[i], done[to[i]] = 1, q.push (to[i]);
	}
	return p;
}

bool dfs (int x, int fa, int target)
{
	if (x == target)
		return 1;
	for (int i = head[x]; i; i=next[i])
		if (to[i] != fa)
		{
			if (dfs (to[i], x, target))
			{
				value[i] = value[i^1] = -1;
				return 1;
			}
		}
	return 0;
}

void dfs2 (int x, int fa)
{
	int t1, t2;
	t1 = t2 = 0;
	f[x] = 0;
	for (int i = head[x]; i; i = next[i])
		if (to[i] != fa)
		{
			dfs2 (to[i], x);
			if (f[to[i]] + value[i] > t1)
			{
				t2 = t1;
				t1 = f[to[i]] + value[i];
			}
			else
				if (f[to[i]] + value[i] > t2)
					t2 = f[to[i]] + value[i];
		}
	f[x] = t1;
	if (Max < t1 + t2)
		Max = t1 + t2, tool = x;
}

int main()
{
	scanf ("%d%d", &n, &k);
	for (int i = 1, a1, a2; i <= n-1; i++)
		scanf ("%d%d", &a1, &a2), add(a1, a2, 1), add(a2, a1, 1);
	ans = 0;
	int now = bfs (1);
	int root = bfs (now);
	ans = d[root] - 1;
	dfs (now, 0, root);
	if (k > 1)
	{
		dfs2 (1, -1);
		ans += Max - 1;
	}
	printf ("%d\n", 2 * (n-1) - ans);
	return 0;
}