记录编号	334027	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十三]逃离遗迹	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.139 s
提交时间	2016-10-31 17:48:54	内存使用	3.96 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define file(x) "escapeb."#x
using std::min;
using std::max;
using std::swap;
const int MAXV=20010;
struct EDGE{int u,v,w;}st[MAXV<<1];
int n,m,hed[MAXV],nxt[MAXV<<1],sz,d[MAXV],s[3];
void _add(int u,int v,int w){
	st[++sz].u=u,st[sz].v=v,st[sz].w=w;
	nxt[sz]=hed[u],hed[u]=sz;
}
void add(int u,int v,int w){
	_add(u,v,w),_add(v,u,w);
}
namespace RMQ{
	int sz,dep[MAXV],f[18][MAXV<<1],th[MAXV];
	void dfs(int u,int fa){
		dep[u]=dep[fa]+1;
		int v;
		f[0][++sz]=u;
		th[u]=sz;
		for(int e=hed[u];e;e=nxt[e]) if((v=st[e].v)!=fa){
			d[v]=d[u]+st[e].w;
			dfs(v,u);
			f[0][++sz]=u;
		}
	}
	bool cmp(int a,int b){return dep[a]<dep[b];}
	void init(){
		dfs(1,0);
		for(int k=1;k<18;k++){
			for(int i=1;i<=sz&&(i+(1<<k)-1<=sz);i++){
				f[k][i]=min(f[k-1][i],f[k-1][i+(1<<k-1)],cmp);
			}
		}
	}
	int lca(int u,int v){
		u=th[u],v=th[v];
		if(u>v) swap(u,v);
		int l=v-u+1,k=0;
		while((1<<k+1)<=l) ++k;
		return min(f[k][u],f[k][v-(1<<k)+1],cmp);
	}
}
int gdis(int u,int v){
	int anc=RMQ::lca(u,v);
	return d[u]+d[v]-(d[anc]<<1);
}
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	scanf("%d%d%d%d",&n,&s[0],&s[1],&s[2]);
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	RMQ::init();
	int idx,dis=1<<30;
	for(int i=1;i<=n;i++){
		int tdis=gdis(s[0],i)+gdis(s[1],i)+gdis(s[2],i);
		if(tdis<dis) dis=tdis,idx=i;
	}
	printf("%d\n%d",idx,dis);
//	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) printf("lca(%d,%d)=%d\n",i,j,RMQ::lca(i,j));
}