小机房的树

【题目描述】

小机房有一棵树，树上有n(1 <= n <= 50000)个节点，标号为0~n-1，有两只虫子分居在两个不同的节点上，他们想爬到一个节点上去，已知从某个节点爬到其父亲节点要花费c(0 <= c <= 1000)精力（从父亲节点爬到此节点也相同），询问它们最少花费多少精力才能到达目标节点。

【输入描述】

第一行输入一个整数n；

接下来n-1行，每行输入三个整数u、v、c，表示从节点u爬到节点v花费c精力；

第n+1行输入一个整数m(1 <= m <= 75000)，表示询问次数；

接下来m行，每行输入两个整数u、v，表示两只虫子所在的节点标号。

【输出描述】

输出m行，每行包含一个整数，表示对于该次询问所得出的答案。

【样例输入】

1 0 1

2 0 1

1 0

2 0

1 2

【样例输出】

源代码：

#include<cstdio>
#include<algorithm>
using namespace std;
struct Node
{
    int S,To,Next;
}Edge[150001];
int n,m,Num(0),i[50001],f[50001][22],Head[50001],Deep[50001];
void Add(int t1,int t2,int t) //边表。
{
    Edge[++Num].To=t2;
    Edge[Num].S=t;
    Edge[Num].Next=Head[t1];
    Head[t1]=Num;
}
void DFS(int T,int S) //DFS预处理深度Deep[]和直系父亲f[][0]，T表示当前节点，S表示当前深度。
{
    Deep[T]=S;
    for (int a=Head[T];a;a=Edge[a].Next)
    {
        int t=Edge[a].To;
        if (!Deep[t]&&t) //防止回溯向上，并特判0。
        {
            f[t][0]=T;
            i[t]=i[T]+Edge[a].S; //i[]表示从根节点到当前节点的距离。
            DFS(t,S+1);
        }
    }
}
void Get_Father() //类似于ST表，记录父系关系，f[i][j]表示i节点的2^j层父亲的节点编号。
{
    for (int b=1;b<=21;b++) //一般不会超过此值。
      for (int a=0;a<n;a++) //节点编号为0~(n-1)。
        f[a][b]=f[f[a][b-1]][b-1]; //2^j层父亲一定就是2^(j-1)层父亲的2^(j-1)层父亲。
}
int Get_Same(int T,int S) //深度调节。
{
    for (int a=0;a<=21;a++)
      if ((1<<a)&S)
        T=f[T][a];
    return T;
}
int LCA(int t1,int t2)
{
    if (Deep[t1]<Deep[t2]) //预处理。
      swap(t1,t2);
    t1=Get_Same(t1,Deep[t1]-Deep[t2]); //使其上升到相同深度。
    for (int a=21;a>=0;a--) //逆序才能由粗到细。
      if (f[t1][a]!=f[t2][a])
      {
        t1=f[t1][a];
        t2=f[t2][a];
      }
    if (t1==t2) //根节点。
      return t1;
    return f[t1][0];
}
int main() //此题节点编号为0~(n-1)。
{
    scanf("%d",&n);
    for (int a=1;a<n;a++)
    {
        int t,t1,t2;
        scanf("%d%d%d",&t1,&t2,&t);
        Add(t1,t2,t);
        Add(t2,t1,t);
    }
    i[0]=0;
    DFS(0,0); //默认根节点为0。
    Get_Father();
    scanf("%d",&m);
    for (int a=0;a<m;a++) //第一次打倍增LCA，QAQ。
    {
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        int Ans=LCA(t1,t2);
        if (Ans==t1) //是否在一条链上。
          printf("%d
",i[t2]-i[t1]);
        else
          printf("%d
",i[t1]+i[t2]-(i[Ans]<<1));
    }
    return 0;
}