洛谷|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

这道题巨难！！

过程

开始想的是求那三个点的LCA，结果果然WA了。

~~ 同为不过样例的代码，怎么我就一个点没过呢（滑稽） ~~

后来看了这个大佬的题解，过程在原文，结论是：

那个点是LCA(a,b),LCA(b,c),LCA(a,c)中深度最大的

花费是deep(a)+deep(b)+deep©?最深LCA的深度?最浅LCA的深度?2（其实就是减a,b,c三个深度，因为有两个LCA是一样的）

“在树上任选三点t1,t2,t3，LCA(t1,t2),LCA(t1,t3),LCA(t2,t3)中一定有两个是相等的。”

然后，在洛谷上过了，一中oj上TLE两个点嘤。

最后用了快读，加了inline，都还过不了

Code

（这份代码没用快读）

#include<bits/stdc++.h>
using namespace std;

const int MAXN=500000*2+5;
int n,m;

struct tu{
	private:
		struct ed{
			int to,nex;
		} e[MAXN];
		int head[MAXN],newp,siz,root,H,f[MAXN][20];
		int depth[MAXN];
		bool bfsed;
		
	public:
		inline void clear(void){
			memset(e,0,sizeof(e));
			memset(head,0,sizeof(head));
			memset(f,0,sizeof(f));
			memset(depth,0,sizeof(depth));
			newp=0;
			siz=0;
			root=1;
			bfsed=0;
		}
		
		inline void vAdd(int p1,int p2){
			++newp;
			e[newp].to=p2;
			e[newp].nex=head[p1];
			head[p1]=newp;
		}
		
		inline void resize(int s){
			siz=s;
			H=(int)(1.0*log(siz)/log(2)+0.5);
		}
		
		inline int size(void){
			return siz;
		}
		
		inline int lca(int p1,int p2){
			if(!bfsed){
				bfs();
			}
			
			if(depth[p1]<depth[p2]){
				swap(p1,p2);
			}
			
			for(int i=H;i>=0;--i){
				if(depth[f[p1][i]]>=depth[p2]){
					p1=f[p1][i];
				}
			}
			
			if(p1==p2)return p1;
			
			for(int i=H;i>=0;--i){
				if(f[p1][i]!=f[p2][i]){
					p1=f[p1][i];
					p2=f[p2][i];
				}
			}
			return f[p1][0];
		}
		
		inline void solve(int x,int y,int z){
			int a,b,c;
			a=lca(x,y);
			b=lca(y,z);
			c=lca(x,z);
			int ans1,ans2;
			if(depth[a]>=depth[b] && depth[a]>=depth[c]){
				ans1=a;
			}
			
			else if(depth[b]>=depth[a] && depth[b]>=depth[c]){
				ans1=b;
			}
			
			else if(depth[c]>=depth[a] && depth[c]>=depth[b]){
				ans1=c;
			}
			int pt1=depth[x]-depth[a];
			int pt2=depth[y]-depth[b];
			int pt3=depth[z]-depth[c];
			ans2=pt1+pt2+pt3;
			printf("%d %d\n",ans1,ans2);
		}
		
		inline void bfs(void){
			queue<int> q;
			q.push(root);
			depth[root]=1;
			while(!q.empty()){
				int x=q.front();
				q.pop();
				for(int i=head[x];i;i=e[i].nex){
					int y=e[i].to;
					
					if(depth[y])continue;
					
					depth[y]=depth[x]+1;
					
					f[y][0]=x;
					
					for(int j=1;j<=H;++j){
						f[y][j]=f[f[y][j-1]][j-1];
					}
					
					q.push(y);
				}
			}
			bfsed=1;
		}
		
		
};

tu a;

int main(void){
	scanf("%d%d",&n,&m);
	a.clear();
	a.resize(n);
	for(int i=1;i<n;++i){
		int p1,p2;
		scanf("%d%d",&p1,&p2);
		a.vAdd(p1,p2);
		a.vAdd(p2,p1);
	}
	
	for(int i=1;i<=m;++i){
		int keke,kaka,waiwai;
		scanf("%d%d%d",&keke,&kaka,&waiwai);
		a.solve(keke,kaka,waiwai);
	}
	
	return 0;
}