LOJ#3347. 「APIO2020」有趣的旅途

Description

• 传送门

Solution

• 以下给出了一个只需要 3 n 3n 3n次询问的做法
• 首先考虑怎么构造一个方案，首先先反过来，然后考虑对于一个起点，把不同儿子的点按照深度从小到大轮流跳。不难发现只要不存在一个子树的大小 > n 2 >\frac{n}{2} >2n​，就一定有解。
• 至于构造方案，设 r e s res res为剩下的点， m x mx mx为最大的子树的大小，当前满足 r e s − m x ≥ m x res-mx\ge mx res−mx≥mx，每一次选择其他子树中最浅的没有被选择的点，那么最后一定有一个时候满足 r e s − m x = m x res-mx=mx res−mx=mx，然后一个简单的思路就是在 m x mx mx和 r e s − m x res-mx res−mx中轮流选即可。
• 这个部分有一点细节，比如最后轮流选要考虑一下有没有更浅的点没有选择。
• 现在我们需要找到重心，以及它的所有儿子，每一个点属于哪一个儿子，以及它的深度。
• 寻找重心的过程可以考虑从根每一次往一个 s z sz sz最大的点走。
• 首先询问以0为根，所有点的深度。
• 然后从0往下面走，当前的点是 x x x，则找到所有 d e p [ y ] = d e p [ x ] + 1 dep[y]=dep[x]+1 dep[y]=dep[x]+1的 y y y，询问它们到 x x x的距离，如果距离是 1 1 1那么就是 x x x的儿子，否则它在父亲的子树内，把 y y y跟 f a x fa_x fax​连一条长度为 d i s − 1 dis-1 dis−1的边。
• 之后询问儿子的 s z sz sz，找到一个最大的走下去。
• 确认重心 x x x之后只需要对于 d e p [ y ] > d e p [ x ] + 1 dep[y]>dep[x]+1 dep[y]>dep[x]+1的 y y y问 y y y到三个儿子中的两个的距离，由于我们知道这三个距离分别是 d , d + 2 , d + 2 d,d+2,d+2 d,d+2,d+2所以知道两个相当于是知道第三个，因此可以直接找到它属于哪一个子树、它到根的距离。
• 一开始 n n n次询问，考虑前一部分的点，找 s z sz sz和 d i s dis dis最多要 2 2 2次，后一部分的点问两个儿子最多要 2 2 2次，因此只需要小于 3 n 3n 3n的操作数即可完成询问。

#include "fun.h"
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 100005
using namespace std;

int dep[maxn],n,vis[maxn],i,j,k;
int em,e[maxn*2],nx[maxn*2],ls[maxn],ec[maxn*2];

int dis(int x,int y){return hoursRequired(x,y);}
int getsz(int x,int y){return attractionsBehind(x,y);}
vector<int> d[maxn];

void insert(int x,int y,int z){
	em++; e[em]=y; nx[em]=ls[x]; ls[x]=em; ec[em]=z;
	em++; e[em]=x; nx[em]=ls[y]; ls[y]=em; ec[em]=z;
}

vector<int> p;

int son[3],cnt,c[3][maxn],D[3][maxn],tot[3],dep0[maxn];
void dfs(int x,int p,int dep,int fr){
	c[fr][dep]++,D[fr][++tot[fr]]=x,dep0[x]=dep;
	for(int i=ls[x];i;i=nx[i]) if (e[i]!=p){
		dfs(e[i],x,dep+ec[i],fr);
	}
}
int cmp(int i,int j){return dep0[i]<dep0[j];}

int sz[3],I[3],now[3],pre,mx,res,prehi;
void push(int id){
	prehi=I[id],p.push_back(D[id][++now[id]]),c[id][I[id]]--,sz[id]--,res--,pre=id;
	while (!c[id][I[id]]&&I[id]<=n) I[id]++;	
}
void add(){
	int id=-1;
	for(k=0;k<cnt;k++) if (k!=pre&&(id==-1||I[k]<I[id])) id=k;
	push(id);
}
void doit(){
	for(k=0;k<cnt;k++) for(i=1;i<=n;i++) sz[k]+=c[k][i];
	for(k=0;k<cnt;k++) I[k]=1,sort(D[k]+1,D[k]+1+tot[k],cmp);
	pre=-1,mx=0,res=0;
	for(k=1;k<cnt;k++) if (sz[k]>sz[mx]) mx=k;
	for(k=0;k<cnt;k++) res+=sz[k];
	if (sz[mx]>res-sz[mx]) push(mx);
	while (1){
		mx=0;for(k=1;k<cnt;k++) if (sz[k]>sz[mx]) mx=k;
		if (sz[mx]==res-sz[mx]){
			if (pre==-1) pre=0;
			if (pre==mx){
				while (sz[mx])
					add(),push(mx);
			} else {
				if (cnt==3){
					int tp=0;
					for(int i=0;i<3;i++) if (i!=mx&&i!=pre){
						if (I[i]<prehi){
							tp=1;
							push(i);
							push(mx);
							break;
						} 
					}
					if (tp) continue;
				}
				while (res){
					push(mx);
					add();
				}
			}
			return;
		}
		add();
	}
}

std::vector<int> createFunTour(int N, int Q) {
	n=N;
	for(i=1;i<n;i++) dep[i]=dis(0,i),d[dep[i]].push_back(i);
	int x=0,pre=-1; vis[0]=1;
	while (1){
		for(i=0;i<d[dep[x]+1].size();i++){
			int y=d[dep[x]+1][i]; vis[y]=1;
			k=dis(y,x);
			if (k==1) insert(x,y,1);
			else insert(y,pre,k-1);
		}
		int sz0=0,id=-1;
		for(i=ls[x];i;i=nx[i]) if (dep[e[i]]>dep[x]){
			k=getsz(x,e[i]);
			if (id==-1||k>sz0) sz0=k,id=e[i];
		}
		if (id!=-1&&sz0>n/2){
			pre=x,x=id;
		} else break;
	}
	for(i=ls[x];i;i=nx[i]) 
		son[cnt++]=e[i];
	static int v[3];
	for(i=0;i<n;i++) if (!vis[i]){
		for(j=0;j<2;j++) v[j]=dis(i,son[j]);
		if (v[0]<v[1]) insert(i,son[0],v[0]); else 
		if (v[1]<v[0]) insert(i,son[1],v[1]); else 
			insert(i,son[2],v[0]-2);
	}
	
	for(i=0;i<cnt;i++) 
		dfs(son[i],x,1,i);
	p.push_back(x);
	doit();	
	for(i=0;i<=(n-1)/2;i++)
		swap(p[i],p[n-1-i]);
	return p;
}