codevs 2370小屋の木(lca)

テーマ説明Description小屋にはファン犬種の木があり、木にはN個のノードがあり、ノード番号は0からN-1で、2匹の虫が漂犬と大吉犬と呼ばれ、2つの異なるノードに分かれている.ある日、彼らは1つのノードに登ってベースを作りたいと思っていましたが、2匹の虫として、あまり精力を費やしたくありません.あるノードから父親ノードに登るにはcのエネルギーがかかることが知られています(父親ノードからこのノードに登るのも同じです).彼らは最も精力を費やした道を見つけて、基礎を作るときに精力を旺盛にしたいと思っています.彼らはあなたがこの道を見つけるためにプログラムを設計して、少なくともどれだけの精力を費やす必要があるかを教えてほしいと思っています.
Input Descriptionの最初の行を記述するnを入力し、次にn−1行の各行に3つの整数u,v,cを持つ.ノードuがノードvに登るのにcの労力がかかることを示す.n+1行目の整数mはm回のクエリを表す.次にm行の各行には2つの整数uがあり、vは2匹の虫がいるノードを表す
出力記述Output Descriptionにはm行があり、各行に整数があり、このクエリに対して得られた最短距離を表す.
サンプル入力Sample Input 3 1 0 1 2 0 1 3 1 0 2 2 2
サンプル出力Sample Output 1 1 2
データ範囲および提示Data Size&Hint 1<=n<=50000,1<=m<=75000,0<=c<=1000
裸のlcaには、息子から父親までの距離を記録したり、ルートノードまでの距離を記録したりする方法がたくさんあります.
2016.10.24:今日は倍増lcaを習ったので、この問題を倍増lcaでもう一度やりました.
コードは次のとおりです.

#include
#include
#include
using namespace std;
const int MAXN=50000+500;
int first[MAXN],nxt[MAXN<<1];
int fa[MAXN],dis[MAXN],deep[MAXN]; 
bool used[MAXN];
int n,m,tot;
struct edge
{
    int from,to,cost;
}es[MAXN<<1];
void build(int f,int t,int d)
{
    es[++tot]=(edge){f,t,d};
    nxt[tot]=first[f];
    first[f]=tot;
}
void init()
{
    memset(first,-1,sizeof(first));
    tot=0;
}
void dfs(int s)// s    ，     
{
    for(int i=first[s];i!=-1;i=nxt[i])
    {
        int v=es[i].to;
        if(!used[v])
        {
            used[v]=1;
            dis[v]=es[i].cost;
            deep[v]=deep[s]+1;
            fa[v]=s;
            dfs(v);
        }
    }
}
int ask(int x,int y)
{
    int ans=0;
    if(deep[x]>deep[y]) swap(x,y);
    while(deep[x]!=deep[y])//    ，        
    {
        ans+=dis[y];
        y=fa[y];
    }
    while(x!=y)//    ，              
    {
        ans+=dis[x]+dis[y];
        x=fa[x];
        y=fa[y];
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    init();
    for(int i=1;i<=n-1;i++)
    {
        int ff,tt,dd;
        scanf("%d%d%d",&ff,&tt,&dd);
        build(ff,tt,dd);
        build(tt,ff,dd);
    }
    fa[0]=0;
    dfs(0);
    scanf("%d",&m);
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d
",ask(x,y));
    }
    return 0;
}

倍増lca:

#include
#include
#include
using namespace std;
const int MAXN=60000;
int first[MAXN],nxt[MAXN<<1];
int deep[MAXN],fa[MAXN],dis[MAXN];
int t[MAXN][30];//t[i][j]  i   2^j       
int n,m,tot;
bool used[MAXN];
struct edge
{
    int from,to,cost;
}es[MAXN<<1];
void init()
{
    memset(first,-1,sizeof(first));
    tot=0;
}
void build(int f,int t,int d)
{
    es[++tot]=(edge){f,t,d};
    nxt[tot]=first[f];
    first[f]=tot;
}
void dfs(int s)
{
    used[s]=1;
    for(int i=first[s];i!=-1;i=nxt[i])
    {
        int v=es[i].to;
        if(!used[v])
        {
            used[v]=1;
            dis[v]=dis[s]+es[i].cost;
            deep[v]=deep[s]+1;
            fa[v]=s;
            dfs(v);
        }
    }
}
int lca(int x,int y)
{
    if(deep[x]>deep[y]) swap(x,y);
    int tt=deep[y]-deep[x];//        
    for(int i=0;i<=20;i++)
        if((1<// tt      ，          
    for(int i=20;i>=0;i--)
        if(t[x][i]!=t[y][i])//   2    ，     
        {
            x=t[x][i];
            y=t[y][i];
        }
    if(x!=y) return fa[x];//       lca lca    
    return x;
}
int main()
{
    init();
    scanf("%d",&n);
    for(int i=1;iint u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        build(u,v,c);
        build(v,u,c);
    }
    dfs(0);
    for(int i=0;i0]=fa[i];//   t[i][0] i    
    for(int i=0;ifor(int j=1;j<=20;j++)
            t[i][j]=t[t[i][j-1]][j-1];//   2^j     2^(j-1)   2^(j-1)  
    scanf("%d",&m);
    while(m--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        int ans=lca(u,v);
        printf("%d
",dis[u]+dis[v]-2*dis[ans]);
    }
    return 0;
}