Description

• 传送门

Solution

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

#include "fun.h"
#include
#include
#include
#include
#include
#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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！