bzoj1602

题解：

简单lca

然而我调了半小时QAQ

lca的时候要判断0

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=;

int ne[N],l,sd[N],f[][N],num[N],tot,fi[N],zz[N],sl[N],jin[N],n,m,x,y,z,chu[N];

void jb(int x,int y,int z)

{

    ne[++tot]=fi[x];

    fi[x]=tot;

    zz[tot]=y;

    sl[tot]=z;

}

void dfs(int x,int y)

{

    jin[x]=++l;

    f[][x]=y;

    for (int i=fi[x];i;i=ne[i])

     if (zz[i]!=y)

      {

          sd[zz[i]]=sd[x]+;

          num[zz[i]]=num[x]+sl[i];

          dfs(zz[i],x);

      }

    chu[x]=++l;

}

int lca(int x,int y)

{

    if (x==y)return x;

    if (sd[x]<sd[y])swap(x,y);

    for (int i=;i>=;i--)

     if (f[i][x]!=&&!(jin[f[i][x]]<=jin[y]&&chu[f[i][x]]>=chu[y]))x=f[i][x];

    return f[][x];

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=;i<n;i++)

     {

         scanf("%d%d%d",&x,&y,&z);

         jb(x,y,z);jb(y,x,z);

     }

    dfs(,);

    for (int i=;i<;i++)

     for (int j=;j<=n;j++)

      f[i][j]=f[i-][f[i-][j]];

    while (m--)

     {

         scanf("%d%d",&x,&y);

         printf("%d\n",num[x]+num[y]-*num[lca(x,y)]);

     }

    return ;

}