题解 [BalticOI 2020 Day2] 村庄

《2021.4.21 校内模拟赛游记》

模拟赛的一题——我整场模拟赛都用来做这题了,所以没有游记了,只剩下一篇题解了。

有一棵树,要让每一个点移动到另一个点,求移动距离和的最大值和最小值。

先考虑最小值,这个移动的下届非常好确定,因为由题目可以知道,每一个点最少要移动一次,所以考虑一下链的情况,就是偶数个的话取到下界,不然一个就要多移动一次。然后考虑菊花图,同样很好确定大小为 nn 的菊花图的最小答案是 2(n1)2(n-1),最大值同样也是这个。

然后就简单了,就把书分成若干条链和菊花图就可以了,一个点儿子多那是没办法,得菊花,不然肯定是变成链的好。至于怎么剖图为链,其实不需要把整条链给拿出来,因为反正我们都是两两配的,先两两配着,若 11 号点多出来了后面再修复一下就可以了。

说着好像很简单的样子,但考场上推了半天,草稿纸上处理了一堆的问题,挺长的时间才想到,赛后口胡和赛场上去独立完成还是有很大的距离的。

那么最大的怎么做呢?赛场上同样考虑了链上的情况,很容易发现把链劈成两半,然后让一边的一定得跨越到另一边就可以了,于是猜想在树上就按照中心或重心之类的分成两半,然后让一边的子树跨到另一边去就可以了。

但是比赛的时候我不知道怎样去确定上界,所以也不清楚到底是中心还是重心,对于多余两个的子树又怎么去处理。

赛后发现其实还是很容易证明的,考虑每一条边最多经过多少次。最多是两边的子树较小的那个的节点个数次乘上 22, 因为小的那个子树里的点全部跑出来,外面最多有这些点跑进去。

那么这个上界能否取到呢?怎么样才会取到呢?其实只要能保证每一条边都能取到必须得是这条边一个点相连的所有子树的和必须要比另一个点的子树要大,不然的话就没有办法确保每一个子树中的点都跑到了和它不相同的子树,也就没有办法确保边被跑满。那么就是要取重心了。

具体的做法也是比较的巧妙的,因为反正没有一个子树大小会超过整个树的一半,那么把它的编号加一半就肯定在另外一棵子树里面了。

代码实现得比较啰嗦,因为把链和菊花图分开存了,为了修正,需要记录 11 号点儿子所在的 菊花图/链 的 下标/迭代器。后来发现其实可以一起处理的(因为都是 2(n1)2(n-1) 啊),但比较懒,就没有改。

#include <cstdio>
#include <vector>
#define int long long
const int N = 100005;
typedef std::vector<int> twt;
typedef std::vector<twt>::iterator IT;
twt g[N];
IT t;
std::vector<twt> fl, tr;
int min, ans[N], n, x, y, t2, t3, t4, max, ans2[N], dfn[N], num, size[N];
bool flag[N];
void dfs(int u, int fa) {
	twt tmp;
	dfn[++num] = u;
	size[u] = 1;
	for(int i = 0; i < (signed)g[u].size(); i++) {
		int v = g[u][i];
		if(v == fa) continue;
		dfs(v, u);
		size[u] += size[v];
		if(flag[v] == 0) tmp.push_back(v);
	}
	if(tmp.size() == 1 || tmp.size() == 2) {
		tmp.push_back(u);
		tr.push_back(tmp);
		flag[u] = 1;
		if(fa == 1) {
			if(tmp.size() == 2) t2 = tr.size()-1;
			else t = --tr.end(), t3 = tr.size()-1;
		}
	}
	else if(tmp.size() > 2) {
		tmp.push_back(u);
		fl.push_back(tmp);
		flag[u] = 1;
		if(fa == 1) t4 = fl.size()-1;
	}
	max += 2*std::min(size[u], n - size[u]);
}
void fix() {
	if(t2 != 0) {
		tr[t2].push_back(1);
		return;
	}
	if(t3 != 0) {
		twt tmp;
		for(int i = 0; i < (signed)tr[t3].size(); i++) tmp.push_back(tr[t3][i]);
		tmp.push_back(1);
		tr.erase(t);
		fl.push_back(tmp);
		return;
	}
	fl[t4].push_back(1);
}
signed main() {
//	freopen("village.in", "r", stdin);
//	freopen("village.out", "w", stdout);
	
	scanf("%lld", &n);
	for(int i = 1; i < n; i++) 
		scanf("%lld%lld", &x, &y), 
		g[x].push_back(y), g[y].push_back(x);
	dfs(1, 0); 
	for(int i = 1; i <= n; i++) ans2[dfn[i]] = dfn[(i+n/2-1)%n+1];
	if(flag[1] == 0) fix();
	for(int i = 0; i < (signed)tr.size(); i++) 
		if(tr[i].size() == 3) {
			tr[i].push_back(tr[i][0]);
			for(int j = 0; j < (signed)tr[i].size()-1; j++)
				ans[tr[i][j]] = tr[i][j+1];
			min += 4;
		}
		else {
			ans[tr[i][0]] = tr[i][1], ans[tr[i][1]] = tr[i][0];
			min += 2;
		}
	for(int i = 0; i < (signed)fl.size(); i++) {
		min += 2 * ((signed)fl[i].size()-1);
		ans[fl[i][0]] = fl[i][1], ans[fl[i][1]] = fl[i][0];
		fl[i].push_back(fl[i][2]);
		for(int j = 2; j < (signed)fl[i].size()-1; j++) ans[fl[i][j]] = fl[i][j+1];
	}
	printf("%lld %lld\n", min, max);
	for(int i = 1; i <= n; i++) printf("%lld ", ans[i]);
	puts("");
	for(int i = 1; i <= n; i++) printf("%lld ", ans2[i]);
	return 0;
}

感觉思维难度其实挺大的,而模拟赛搬题人却说思维难度不高,NOIP -……