[POI2011]Inspekcja

题目大意：

给你一棵\(n(n\le10^6)\)个点的树，\(s\)为起点。每次选择一个点作为目标点\(t_i\)，沿最短路走到\(t_i\)再走回\(s\)（最后一次除外）。相邻两次行动不能经过相同的边。问将每一个点作为\(s\)，是否存在一种方案使得除\(s\)外的所有结点都作为目标点被恰好访问一次，如果是，求最小路径和。

思路：

存在合法方案当且仅当去掉\(s\)后剩下的连通块中，最大的连通块大小不超过其余连通块大小之和。

这样的点一定是重心（反过来不一定），因此最多就不超过两个。

答案就是以这个点为根后所有点深度和×2-最大深度。

注意如果恰好有一个子树大小为\(\frac n2\)，则最后删掉的深度一定在这棵子树中。

源代码：

#include<cstdio>

#include<cctype>

#include<vector>

#include<climits>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

typedef long long int64;

const int N=1e6+1;

std::vector<int> e[N];

inline void add_edge(const int &u,const int &v) {

	e[u].push_back(v);

	e[v].push_back(u);

}

int n,size[N],max[N],dep[N],far[N];

void dfs1(const int &x,const int &par) {

	size[x]=1;

	for(unsigned i=0;i<e[x].size();i++) {

		const int &y=e[x][i];

		if(y==par) continue;

		dfs1(y,x);

		size[x]+=size[y];

		max[x]=std::max(max[x],size[y]);

	}

	max[x]=std::max(max[x],n-size[x]);

}

void dfs2(const int &x,const int &par) {

	far[x]=0;

	size[x]=1;

	dep[x]=dep[par]+1;

	for(unsigned i=0;i<e[x].size();i++) {

		const int &y=e[x][i];

		if(y==par) continue;

		dfs2(y,x);

		size[x]+=size[y];

		far[x]=std::max(far[x],far[y]+1);

	}

}

int main() {

	n=getint();

	max[0]=n+1;

	dep[0]=-1;

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

		add_edge(getint(),getint());

	}

	dfs1(1,0);

	for(register int x=1;x<=n;x++) {

		if(max[x]>n/2) {

			puts("-1");

			continue;

		}

		dfs2(x,0);

		int max=0;

		int64 sum=0;

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

			sum+=dep[i];

			max=std::max(max,dep[i]);

		}

		for(register unsigned i=0;i<e[x].size();i++) {

			const int &y=e[x][i];

			if(size[y]==n/2) max=far[y]+1;

		}

		printf("%lld\n",sum*2-max);

	}

	return 0;

}

巴特西

[POI2011]Inspekcja

[POI2011]Inspekcja

题目大意：

思路：

源代码：

最新文章

热门文章