Description
There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.
在线倍增求LCA模板，学习了黄学长的bin[]数组
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define N 41000
#define M 81000
using namespace std;
int n,m,t,mx;
int fa[N][30],deep[N],bin[50];
long long dis[N];
int read()
{
char ch=getchar();int re=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
int head[N],to[M],data[M],nxt[M],cnt;
void clear()
{
cnt=0;
memset(head,0,sizeof(head));
memset(dis,0,sizeof(dis));
memset(deep,0,sizeof(deep));
memset(fa,0,sizeof(fa));
}
void add(int x,int y,int z)
{
to[++cnt]=y;
data[cnt]=z;
nxt[cnt]=head[x];
head[x]=cnt;
}
void dfs(int x,int pre)
{
int i,y;
for(i=head[x];i;i=nxt[i])
{
y=to[i];
if(y==pre) continue;
deep[y]=deep[x]+1;
dis[y]=dis[x]+data[i];
fa[y][0]=x;
dfs(y,x);
}
}
int getbin()
{
bin[0]=1;
for(int i=1;i<=20;i++)
bin[i]=bin[i-1]<<1;
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for(int i=0;bin[i]<=t;i++)
if(t&bin[i]) x=fa[x][i];
if(x==y) return x;
for(int i=mx;i>=0;i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int main()
{
t=read();
getbin();
while(t--)
{
clear();
n=read();m=read();
int i,j,k1,k2,k3;
for(i=1;i<n;i++)
{
k1=read();k2=read();k3=read();
add(k1,k2,k3);add(k2,k1,k3);
}
dfs(1,0);
for(i=0;i<=17;i++)
if(bin[i]>=n)
{
mx=i;
break;
}
for(i=1;i<=mx;i++)
for(j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
for(i=1;i<=m;i++)
{
k1=read();k2=read();
int tmp=lca(k1,k2);
printf("%lld\n",dis[k1]+dis[k2]-(dis[tmp]<<1));
}
}
return 0;
}