luogu3629 [APIO2010]巡逻

创造一个环出来，可以让环上的边都只访问一次。

对于 \(k=1\)，答案就是树的直径两边连起来。

倘若 \(k=2\)，那就先按照 \(k=1\) 的求一遍，然后我们发现，如果第二条加的边构成的环和第一条加的边构成的环有交，那么交必定会被访问两次。这样交不但没有减少访问次数，还抵消了第一次的成果。因此把第一次求出来的直径上的边权值由 \(1\) 变成 \(-1\) 再求一遍。

#include <iostream>

#include <cstdio>

using namespace std;

int n, k, uu, vv, hea[100005], cnt, len, zui[100005], cii[100005], zu=0;

const int oo=0x3f3f3f3f;

struct Edge{

	int too, nxt, val;

}edge[200005];

void add_edge(int fro, int too){

	edge[++cnt].nxt = hea[fro];

	edge[cnt].too = too;

	edge[cnt].val = 1;

	hea[fro] = cnt;

}

int dfs(int x, int f){

	int maxi1=0, maxi2=0, qwq=0;

	cii[x] = zui[x] = 0;

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(t!=f){

			int tmp=dfs(t, x)+edge[i].val;

			if(tmp>maxi1){

				maxi2 = maxi1;

				maxi1 = tmp;

				cii[x] = zui[x];

				zui[x] = i;

			}

			else if(tmp>maxi2){

				maxi2 = tmp;

				cii[x] = i;

			}

		}

	}

	if(maxi1+maxi2>len){

		len = maxi1+maxi2;

		zu = x;

	}

	return maxi1;

}

void debug(int x, int f){

	if(zui[x]){

		edge[zui[x]].val = -1;

		debug(edge[zui[x]].too, x);

	}

	if(cii[x]){

		edge[cii[x]].val = -1;

		debug(edge[cii[x]].too, x);

	}

}

int main(){

	cin>>n>>k;

	for(int i=1; i<n; i++){

		scanf("%d %d", &uu, &vv);

		add_edge(uu, vv);

		add_edge(vv, uu);

	}

	len = 0;

	dfs(1, 0);

	int ans=2*(n-1)-(len-1);

	if(k==2){

		for(int i=zui[zu]; i; i=zui[edge[i].too])

			edge[i].val = edge[((i-1)^1)+1].val = -1;

		for(int i=cii[zu]; i; i=zui[edge[i].too])

			edge[i].val = edge[((i-1)^1)+1].val = -1;

		len = 0;

		dfs(1, 0);

		ans = ans - (len - 1);

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

luogu3629 [APIO2010]巡逻

最新文章

热门文章