HDU2586 How far away ？

LCA-ST算法

题目传送门

刚学LCA的蒟蒻的我，只能找找模板题练练手喽o(╯□╰)o

给你一棵树及各个边的权值，Q个询问求x到y的最小代价。

直接ST上去就把它干翻#手动滑稽（Tarjan仍然在学，原谅蒟蒻的我）（已经填坑2017.10.6）

求x到y的最小代价，可以转化为从根节点到x的距离加上到y的距离减去两倍到LCA的距离。然后只要求出LCA就可以啦！

LCA不会？来自本蒟蒻的Blog

蒟蒻代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 40000
using namespace std;
struct edge{
    int next;
    int to;
    int dis;
};
int fa[MAXN+][],h[MAXN+],dis[MAXN+],depth[MAXN+];
int n,m,k,u,v,d,t;
edge ed[MAXN*2+];
void read(int x,int y,int z){
    k++;
    ed[k].next=h[x];
    ed[k].to=y;
    ed[k].dis=z;
    h[x]=k;
}
void dfs(int x){
    for (int i=h[x];i;i=ed[i].next)
        if (ed[i].to!=fa[x][]){
            int now=ed[i].to;
            fa[now][]=x;
            depth[now]=depth[x]+;
            dis[now]=dis[x]+ed[i].dis;
            dfs(now);
        }
}
void findfather(){
    for (int j=;j<=;j++)
        for (int i=;i<=n;i++)
            fa[i][j]=fa[fa[i][j-]][j-];
}
int LCA(int x,int y){
    if (depth[x]<depth[y]) swap(x,y);
    for (int i=;i>=;i--)
        if (depth[fa[x][i]]>=depth[y]) x=fa[x][i];
    if (x==y) return x;
    for (int i=;i>=;i--)
        if (fa[x][i]!=fa[y][i]){
            x=fa[x][i]; y=fa[y][i];
        }
    return fa[x][];
}
int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d%d",&n,&m);
        memset(h,,sizeof(h));
        k=;
        for (int i=;i<n;i++){
            scanf("%d%d%d",&u,&v,&d);
            read(u,v,d);
            read(v,u,d);
        }
        fa[][]=; depth[]=; dis[]=;
        dfs(); 
        findfather();
        for (int i=;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            int lca=LCA(x,y);
            printf("%d\n",dis[x]+dis[y]-dis[lca]-dis[lca]);
        }
    }
    return ;
}