记录编号	241933	评测结果	AAAAAAAAWW
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	80
用户昵称	God-Nan	是否通过	未通过
代码语言	C++	运行时间	0.655 s
提交时间	2016-03-26 10:49:36	内存使用	25.11 MiB

#include<cstdio>
#include<iostream>
using namespace std;
int head[210000],nextt[420000],to[420000],power[420000],star;
int father[200001][20],deep[210000];
int clearlove(int a,int b);
long long dis[410000];
int n,m;
void addpoint(int f,int t,int p);
void cool(int u);
int main()
{
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
	int i,p,k,l,f,t;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	head[i]=-1;
	for(i=1;i<=n;i++)
	for(p=1;p<=19;p++)
	father[i][p]=-1;
	
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&f,&t,&p);
		addpoint(f,t,p);
		addpoint(t,f,p);
	}
	deep[1]=1;
	cool(1);
	for(i=1;(i<<i)<=n;i++)
	 for(p=1;p<=n;p++)
	   if(father[p][i-1]!=-1)
	    father[p][i]=father[father[p][i-1]][i-1];
	  
	  scanf("%d",&m);
	  int fa;long long ans;
	 for(i=1;i<=m;i++)
	 {
	 	scanf("%d%d",&f,&t);
	    fa=clearlove(f,t);
		   ans=dis[f]+dis[t]-2*dis[fa];
		   printf("%lld\n",ans);
	 }
	    
	return 0;
}
void addpoint(int f,int t,int p)
{
	nextt[++star]=head[f];
	head[f]=star;
	to[star]=t;
	power[star]=p;
	return ;
}
void cool(int u)
{
	int point;
	point=head[u];
	while(point!=-1)
	{
		if(!deep[to[point]])
		{
			deep[to[point]]=deep[u]+1;
			father[to[point]][0]=u;
			dis[to[point]]=dis[u]+power[point];
			cool(to[point]);
		}
		point=nextt[point];
	}
}
int clearlove(int a,int b)
{
	int i,p;
	if(deep[a]<deep[b])
	swap(a,b);
	for(i=0;(1<<i)<=deep[a];i++);
	  
	 i=i-1; 
	 
	 for(p=i;p>=0;p--)
	 if(deep[a]-(1<<p)>=deep[b])
	  a=father[a][p];
	 
	 if(a==b)
	 return a;
	 
	 for(p=i;p>=0;p--)
	 if(father[a][p]!=-1&&father[a][p]!=father[b][p])
	 {
	  a=father[a][p];
	  b=father[b][p];
     }
     return father[a][0];
}