【APIO2010】【樹的直徑】巡邏

當k = 1的時候，顯然直接求出樹的直徑後減去路徑上權值即可

當k = 2的時候，我們可以先dfs出樹的直徑，然後将路徑中的每一條路權值賦為-1，再求一次直徑，把兩次的直徑長度減去，ans = ((n - 1) << 1) - len

關于樹的直徑的求法，可以使用樹的一個性質:樹的直徑的長度一定會是某個點的最長距離f[i]與次長距離g[i]之和。于是可以使用一次dfs求出次短路和最短路和的最大值即為樹的直徑。

代碼:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100000 + 10;
struct Edge
{
	int len,pos;
	int next;
}E[maxn<<1];
int f[maxn],path1[maxn],path2[maxn];
int head[maxn];
int n,k,NE;
int tool,maxlen;

void init()
{
	freopen("patrol.in","r",stdin);
	freopen("patrol.out","w",stdout);
}

void add(int u,int v)
{
	E[NE].len = 1;E[NE].pos = v;
	E[NE].next = head[u];
	head[u] = NE++;
}

void dfs(int u,int pre)
{
	int t1 = 0,t2 = 0;
	f[u] = 0;
	path1[u] = path2[u] = -1;
	for(int i = head[u];i != -1;i = E[i].next)
	{
		int v = E[i].pos;
		if(v != pre)
		{
			dfs(v,u);
			if(f[v] + E[i].len > t1)
			{
				t2 = t1,t1 = f[v] + E[i].len;
				path2[u] = path1[u];
				path1[u] = i;
			}
			else if(f[v] + E[i].len > t2)
			{
				t2 = f[v] + E[i].len;
				path2[u] = i;
			}
		}
	}
	f[u] = t1;
	if(maxlen < t1 + t2)
	{
		maxlen = t1 + t2;
		tool = u;
	}
}

void readdata()
{
	memset(E,0,sizeof(E));
	memset(head,-1,sizeof(head));
	NE = 0;
	scanf("%d%d",&n,&k);
	for(int i = 1;i < n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
}

void solve()
{
	maxlen = 0;
	dfs(1,-1);
	int ans = maxlen - 1;
	for(int i = path1[tool];i != -1;i = path1[E[i].pos])E[i].len = E[i ^ 1].len = -1;
	for(int i = path2[tool];i != -1;i = path1[E[i].pos])E[i].len = E[i ^ 1].len = -1;
	if(k > 1)
	{
		maxlen = 0;
		dfs(1,-1);
		ans += maxlen - 1;
	}
	ans = ((n - 1) << 1) - ans;
	printf("%d\n",ans);
}

int main()
{
	init();
	readdata();
	solve();
	return 0;
}