记录编号	201668	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.783 s
提交时间	2015-10-31 06:31:48	内存使用	48.42 MiB

#include<cstdio>

#define maxn 100010

using namespace std;

typedef long long ll;
ll n,m,father[maxn][30],dis[maxn][30],b[maxn],deep[maxn],tot;
bool vis[maxn];

struct at{
    ll x,y,w,last;
}a[maxn<<1];

void add(ll x,ll y,ll w)
{
    tot++;
    a[tot].x=x;
    a[tot].y=y;
    a[tot].w=w;
    a[tot].last=b[x];
    b[x]=tot;
}

inline void Swap(ll &x,ll &y)
{
    ll c=x;x=y;y=c;
    return;
}

void dfs(ll x)
{
    vis[x]=1;
    for(ll k=1;k<=20;k++){
        father[x][k]=father[father[x][k-1]][k-1];
        dis[x][k]=dis[x][k-1]+dis[father[x][k-1]][k-1];
    }
    for(ll i=b[x];i;i=a[i].last){
        ll v=a[i].y;
        if(!vis[v]){
            deep[v]=deep[x]+1;
            father[v][0]=x;dis[v][0]=a[i].w;
            dfs(v);
        }
    }
    return;
}

ll getlca(ll x,ll y)
{
    ll ans=0;
    if(deep[x]>deep[y]){
        Swap(x,y);
    }
    for(ll k=20;k>=0;k--){
        if(deep[father[y][k]]>=deep[x]){
            ans+=dis[y][k];
            y=father[y][k];
        }
    }
    if(x==y)    return ans;
    for(ll k=20;k>=0;k--){
        if(father[x][k]!=father[y][k]){
            ans+=dis[x][k]+dis[y][k];
            x=father[x][k];
            y=father[y][k];
        }
    }
    ans+=dis[x][0]+dis[y][0];
    return ans;
}

int main()
{
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
    scanf("%lld%lld",&n,&n);
    n++;
    for(ll i=1;i<n;i++){
        ll x,y,w;
        scanf("%lld%lld%lld",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
    scanf("%lld",&m);
    dfs(1);
    for(ll i=1;i<=m;i++){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        printf("%lld\n",getlca(x,y));
    }
    return 0;
}