记录编号	257732	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	0.735 s
提交时间	2016-05-02 16:36:38	内存使用	15.31 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=200100;
int n,len=0,head[maxn],dep[maxn],tim[maxn],dis[maxn],first[maxn],f[maxn][20],tot=0;
bool fe[maxn];
void dfs(int,int);
int d=1;
struct Edge
{
    int next,to,dis;    
}e[maxn];
int qiu(int),t,la;
void Insert(int,int,int);
int  getz(int x,int y);
void yu();
int os()
{
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
    mem(head,-1);
    mem(dis,0);
    mem(fe,0);
    dis[1]=0;
    int q;
    scanf("%d%d",&n,&t);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        Insert(x,y,z);
        Insert(y,x,z);
    }
    scanf("%d",&q);
    dfs(1,1);
    yu();
    for(int i=1;i<=q;i++)
    {
        int s,t;
        scanf("%d%d",&s,&t);
        int z=getz(first[s],first[t]);
        z=tim[z];
        printf("%d\n",dis[s]+dis[t]-2*dis[z]);
    }
}
void Insert(int x,int y,int z)
{
    len++;
    e[len].to=y;
    e[len].dis=z;
    e[len].next=head[x];
    head[x]=len;
}
void dfs(int x,int dp)
{
    tot++;
    fe[x]=1;tim[tot]=x;dep[tot]=dp;first[x]=tot;
    for(int i=head[x];i!=-1;i=e[i].next)
    {
        int k=e[i].to;
        if(fe[k]==0)
        {
            dis[k]=e[i].dis+dis[x];
            dfs(k,dp+1);
            tim[++tot]=x;dep[tot]=dp;
        }
    }
}
void yu()
{
    for(int i=1;i<=2*n-1;i++)
    {
        f[i][0]=i;
    }
    int m=qiu(2*n-1);
    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<=2*n-1;i++)
        {
            int m=1<<(j-1);int y=0;
            int x=f[i][j-1];
            f[i][j]=x;if(i+m<=2*n-1)y=f[i+(1<<(j-1))][j-1];
            if(dep[x]>dep[y]) f[i][j]=y;
            //else f[i][j]=y;
        }
    }    
}
int getz(int s,int t)
{
    if(s>t)swap(s,t);
    int k=qiu(t-s+1);
    int x=f[s][k],y=f[t-(1<<k)+1][k];
    if(dep[x]<dep[y])return x;
    else return y;
}
int qiu(int x)
{    int h=2,ci=0;
    while(h<=x)
    {
        h*=2;ci++;
    }
    return ci;
}
int ww=os();
int main()
{
	;
}