USACO的某题，关于LCA

大概是奶牛的聚会吧.

题目叙述（凭本人记忆） 牧场上的牛们总是要聚会，整个牧场被M条边连着，一共N个牧场，道路长度不一样，问两只牛想要相遇的最短距离是多少，一共Q个查询。
题解：其实是个LCA的模板题，用一个g数组表示从i号节点向上飞2^j步用多少距离 转移方程神似F g[i][j]=g[f[i][j-1]][j-1]+g[i][j-1]先飞到一半 也就是g[i][j-1],再飞一下飞到终点，从f[i][j-1]起飞。
在统一x与y深度的时候就要加上飞过去的g值，在大家双飞（大雾）的时候两个一起加.
最后结果加上g[x][0],f[x][0]就很ok了。处理深度的细节我觉得也没什么特别好多说的，根深度其实感觉还是选1比较好点.选0会和飞出去是一样的.
以下是代码

#include <iostream>
#include <algorithm>
using namespace std;
int N,Q;
int u[20005];
int v[20005];
int w[20005];
int first[20005];
int nex[20005];
int vis[20005];
int f[20005][20];
int g[20005][20];
int d[10005];
int tot;
void add(int x,int y,int z)
{
    u[++tot]=x;
    v[tot]=y;
    w[tot]=z;
    nex[tot]=first[x];
    first[x]=tot;
}
void dfs(int x)
{
//  cout<<x<<'\n';
    vis[x]=1;
    int k=first[x];
    while(k!=-1)
    {
        if(vis[v[k]])
        {
            k=nex[k];
            continue;
        }
        d[v[k]]=d[x]+1;
        f[v[k]][0]=x;
        g[v[k]][0]=w[k];
    //  cout<<x<<' '<<v[k]<<' '<<f[v[k]][0]<<' '<<g[v[k]][0]<<'\n';
        dfs(v[k]);
        k=nex[k];
    }
}
int LCA(int x,int y)
{
    int i,j;
    int ans=0;
    if(d[x]<d[y])
    swap(x,y);
    for(i=18;i>=0;i--)
    {
        if(d[f[x][i]]>=d[y])
        {
            ans+=g[x][i];
            x=f[x][i];
        }
    }
    if(x==y)
    return ans;
    for(i=18;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            ans+=g[y][i];
            ans+=g[x][i];
            x=f[x][i];
            y=f[y][i];
        }
    }
//  cout<<ans<<'\n';
    ans+=g[x][0];
    ans+=g[y][0];
    return ans;
}
int main()
{
    int i,j,k;
    cin>>N>>Q;
    for(i=1;i<=N;i++)
    {
        first[i]=-1;
        nex[i]=-1;
    }
    for(i=1;i<=N-1;i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    d[1]=1;
    dfs(1);
    for(j=1;j<=18;j++)
    {
        for(i=1;i<=N;i++)
        {
            f[i][j]=f[f[i][j-1]][j-1];
            g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1];
        }
    }
    
    for(i=1;i<=Q;i++)
    {
        int a,b;
        cin>>a>>b;
        cout<<LCA(a,b)<<'\n';
    }
}