[AHOI2008]紧急集合 / 聚会

P4281 [AHOI2008]紧急集合 / 聚会

题目描述

欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有N个等待点，有N-1条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在N个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

输入输出格式

输入格式：

第一行两个正整数N和M（N<=500000，M<=500000），之间用一个空格隔开。分别表示等待点的个数（等待点也从1到N进行编号）和获奖所需要完成集合的次数。随后有N-1行，每行用两个正整数A和B，之间用一个空格隔开，表示编号为A和编号为B的等待点之间有一条路。接着还有M行，每行用三个正整数表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

输出格式：

一共有M行，每行两个数P,C，用一个空格隔开。其中第i行表示第i次集合点选择在编号为P的等待点，集合总共的花费是C个游戏币。

输入输出样例

输入样例#1：

输出样例#1：

说明

提示：

40%的数据中N<=2000，M<=2000
100%的数据中，N<=500000，M<=500000

几乎裸的板子题

相会点只有三个，一个是ab的LCA，一个是ac的LCA，另一个是bc的LCA

这个的原因是到两个点的LCA再往别的地方走路径就需要×2，很显然另一个点往这个LCA走最近

勉强卡过了luogu测评机，但没能卡过loj测评机

上代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dwn(i,a,b) for(int i=a;i>=b;i--)
#define MAXN 500050
#define MAXM 1000050
using namespace std;
int to[MAXM],nxt[MAXM],fir[MAXN],tot,dp[MAXN][25],n,m,dep[MAXN];
void ade(int u,int v){
	to[++tot]=v;
	nxt[tot]=fir[u];
	fir[u]=tot;
}
void get_tree(int x,int fa){
	dp[x][0]=fa; dep[x]=dep[fa]+1;
	rep(i,1,23) dp[x][i]=dp[dp[x][i-1]][i-1];
	for(int k=fir[x];k;k=nxt[k]){
		if(to[k]!=fa) get_tree(to[k],x);
	}
}
struct zlk{
	int x,y;
}ans[4];
int LCA(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	dwn(i,23,0) if(dep[dp[x][i]]>=dep[y]) x=dp[x][i];
	if(x==y) return x;
	dwn(i,23,0) if(dp[x][i]!=dp[y][i]) x=dp[x][i],y=dp[y][i];
	return dp[x][0];
}
bool cmpp(zlk q,zlk w){return q.y<w.y;}
int read(){
	int x=0;
	char ch=getchar();
	while('0'>ch || ch>'9') ch=getchar();
	while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x;
}
void print(int x){
	if(x==0){putchar('0'); return;}
	int tots=1;while(x>=tots) tots*=10;tots/=10;
	while(tots>0) putchar('0'+x/tots),x%=tots,tots/=10;
}
int main(){
	scanf("%d%d",&n,&m);
	rep(i,1,n-1){
		int a=read(),b=read();
		ade(a,b); ade(b,a);
	}
	get_tree(1,0);
	rep(i,1,m){
		int a=read(),b=read(),c=read();
		int d=LCA(a,b),e=LCA(b,c),f=LCA(a,c),k=LCA(d,c);
		ans[1].x=d; ans[1].y=dep[a]-dep[d]+dep[b]-dep[d]+dep[c]-dep[k]+dep[d]-dep[k];
		ans[2].y=dep[b]-dep[e]+dep[c]-dep[e]+dep[a]-dep[k]+dep[e]-dep[k]; ans[2].x=e;
		ans[3].x=f; ans[3].y=dep[a]-dep[f]+dep[c]-dep[f]+dep[b]-dep[k]+dep[f]-dep[k];
		sort(ans+1,ans+4,cmpp);
		print(ans[1].x); putchar(" "); print(ans[1].y); puts("");
	}
	return 0;
}