自动搬运

查看原文

来自洛谷，原作者为

	jr_linys 人要学会认识自己

搬运于2025-08-24 22:54:43，当前版本为作者最后更新于2024-01-24 16:42:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10105 [GDKOI2023 提高组] 游戏
去年Day2爆零打铜，今年又打铜。当时锯材务必的我赛后这题搞了两星期。

给出的 $3$ 个距离对应的路径的交汇点为中心点，设中心点到那三个点的距离为 $x,y,z$。

可得

然后可用换根 DP 查找每个点的最长链、次长链、次次长链来自哪里，维护儿子方最长链、到根节点路径的倍增。

接着对一个询问，找到满足最长链、次长链的限制下次次长链最长的中心点，这是一个二维偏序问题。

#include<bits/stdc++.h>
using namespace std;
int read(){//哮哮快读
	char c;
	while(c=getchar(),c<'0'||c>'9');
	int x=c^'0';
	while(c=getchar(),c>='0'&&c<='9') x=x*10+(c^'0');
	return x;
}
const int N=2e5,M=18;
int n,logn,q,m,cnt;
int dep[N+5],siz[N+5][3],fr[N+5][3],zz[N+5][3];
int dss[N+5][2],ds[N+5][M],fa[N+5][M];
vector<int> g[N+5];

struct stu{int x,y,z,id;}dot[N+5],qs[N+5];
bool cmp(stu a,stu b){
	if(a.y==b.y) a.x>b.x;
	return a.y>b.y;
}
struct stu2{int x,id;}fuc[N+5];
bool cmp2(stu2 a,stu2 b){return a.x>b.x;}
int ans[N+5][3],xid[N+5];

void dfs1(int u,int fat){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v!=fat){
			dep[v]=dep[u]+1;
			fa[v][0]=u;
			for(int i=1;i<=logn;i++) fa[v][i]=fa[fa[v][i-1]][i-1];//父节点方向倍增
			dfs1(v,u);
			
			for(int i=0;i<3;i++){
				if(siz[v][0]+1>siz[u][i]){
					for(int j=2;j>i;j--) siz[u][j]=siz[u][j-1],fr[u][j]=fr[u][j-1],zz[u][j]=zz[u][j-1];
					siz[u][i]=siz[v][0]+1,fr[u][i]=v,zz[u][i]=u;
					break; 
				}
			}
		}
	}
	ds[u][0]=dss[u][0]=fr[u][0],dss[u][1]=fr[u][1];//重子链和次重子链方向
	for(int i=1;i<=logn;i++) ds[u][i]=ds[ds[u][i-1]][i-1];//重子链倍增
}
void dfs2(int u,int fat){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v!=fat){
			int sizu,zzu;//换根，处理来自父节点方向的最长连
			if(fr[u][0]==v) sizu=siz[u][1]+1,zzu=zz[u][1];
			else sizu=siz[u][0]+1,zzu=zz[u][0];
			for(int i=0;i<3;i++){
				if(sizu>siz[v][i]){
					for(int j=2;j>i;j--) siz[v][j]=siz[v][j-1],fr[v][j]=fr[v][j-1],zz[v][j]=zz[v][j-1];
					siz[v][i]=sizu,fr[v][i]=u,zz[v][i]=zzu;
					break;
				}
			}
			dfs2(v,u);
		}
	}
	dot[++cnt]={siz[u][0],siz[u][1],siz[u][2],u};//储存三元组+id
}

int trs[N+5],tri[N+5];
void upd(int x,int s,int id){//树状数组，trs为最大第三长链，tri为中心点
	for(;x<=n;x+=x&-x) if(s>trs[x]) trs[x]=s,tri[x]=id;
}
int ask(int x){
	int s=-1,id=0;
	for(;x;x-=x&-x) if(trs[x]>s) s=trs[x],id=tri[x];
	return id;//求的是中心点
}
int find(int x){//找到最长连符合条件的范围
	int l=1,r=n+1;
	while(r-l>1){
		int mid=l+r>>1;
		fuc[mid].x>=x? l=mid:r=mid;
	}return l;
}
int line(int u,int d,int x){
	if(!x) return u;
	int z=zz[u][d],len=dep[u]-dep[z],ans=u;
	if(x<=len){//在起点一侧
		for(int i=logn,y=(1<<logn);i>=0;i--,y>>=1) if(x&y) ans=fa[ans][i];
	}else{//在另一侧
		int fs=u;
		if(len){//转折点非自身
			for(int i=logn,y=(1<<logn);i>=0;i--,y>>=1) if((len-1)&y) fs=fa[fs][i];
			d=(dss[z][0]==fs);
		}else d=(fr[u][d]!=dss[u][0]);//转折点是自身
		x-=len+1,ans=dss[z][d];//跳到转折点的 重儿子/次重儿子
		for(int i=logn,y=(1<<logn);i>=0;i--,y>>=1) if(x&y) ans=ds[ans][i];//倍增
	}
	return ans;
}
int main(){
	memset(trs,-1,sizeof(trs));//初始值要为-1,不然为第三长为0的不会更新
	n=read(),logn=__lg(n);
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		g[u].push_back(v),g[v].push_back(u);
	}
	
	dfs1(1,-1),dfs2(1,-1);
	
	//对最长连进行离散化，以便用树状数组维护
	sort(dot+1,dot+1+n,cmp);
	fuc[1]={dot[1].x,1};
	for(int i=2;i<=n;i++) fuc[i]={dot[i].x,i};
	sort(fuc+1,fuc+1+n,cmp2);
	for(int i=1;i<=n;i++) xid[fuc[i].id]=i;
	
	q=read();
	for(int i=1;i<=q;i++){
		int x=read(),y=read(),z=read();
		x=x+y-z>>1,y-=x,z-=y,swap(y,z);
		ans[i][1]=1,ans[i][2]=2;
		if(x<y) swap(x,y),swap(ans[i][0],ans[i][1]);
		if(x<z) swap(x,z),swap(ans[i][0],ans[i][2]);
		if(y<z) swap(y,z),swap(ans[i][1],ans[i][2]);
		qs[i]={x,y,z,i};
	}
	sort(qs+1,qs+1+q,cmp);
	cnt=1;
	for(int i=1;i<=q;i++){
		int x=qs[i].x,y=qs[i].y,z=qs[i].z,id=qs[i].id;
		while(cnt<=n&&dot[cnt].y>=y) upd(xid[cnt],dot[cnt].z,dot[cnt].id),cnt++;
		int u=ask(find(x));
		int sss[3]={ans[id][0],ans[id][1],ans[id][2]};
		ans[id][sss[0]]=line(u,0,x),ans[id][sss[1]]=line(u,1,y),ans[id][sss[2]]=line(u,2,z);
	}
	for(int i=1;i<=q;i++) printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
}