HDU 2586 How far away

LCA（在线）

#include"iostream"
#include"cstring"
using namespace std;
const int maxn=4e4+5;
int N,Q;
int dp[maxn<<1][20];//保存cnt节点区间里深度最小的节点
struct Edge
{
    int t,next,v;
};
Edge E[maxn<<1];
int head[maxn],tot;
int dep[maxn<<1];
int First[maxn];//第cnt个节点是哪个点
int cnt;//遍历的第cnt个节点
int id[maxn<<1];//第cnt个节点是原来树上的第几个
void AddEdge(int aa,int bb,int v)
{
    E[++tot].t=bb;
    E[tot].v=v;
    E[tot].next=head[aa];
    head[aa]=tot;
}
void dfs(int u,int pre,int deep)
{
    id[++cnt]=u;
    First[u]=cnt;
    dep[cnt]=deep;
    dp[cnt][0]=cnt;
    for(int i=head[u];i!=-1;i=E[i].next)
    {
        int t=E[i].t;
        int v=E[i].v;
        if(t==pre)continue;
        dfs(t,u,deep+v);
        id[++cnt]=u;
        dep[cnt]=deep;
        dp[cnt][0]=cnt;
    }
}
void RMQ_ST()
{
    for(int j=1;(1<<j)<=cnt;j++)
    {
        for(int i=1;i+(1<<j)-1<=cnt;i++)
        {
            int cnt1=dp[i][j-1],cnt2=dp[i+(1<<(j-1))][j-1];
            if(dep[cnt1]<dep[cnt2])dp[i][j]=cnt1;
            else dp[i][j]=cnt2;
        }
    }
}
int query(int L,int R)
{
    L=First[L];
    R=First[R];
    if(L>R)swap(L,R);
    int k=0;
    while(1<<(k+1)<(R-L+1))k++;
    int cnt1=dp[L][k],cnt2=dp[R-(1<<k)+1][k];
    if(dep[cnt1]<dep[cnt2])return id[cnt1];
    else return id[cnt2];
}
void printid(int L,int R)
{
    for(int i=L;i<=R;i++)cout<<id[i]<<" ";
    cout<<"\n";
    for(int i=L;i<=R;i++)cout<<dep[i]<<" ";
    cout<<"\n\n";
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>N>>Q;
        tot=0;
        cnt=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<N;i++)
        {
            int t1,t2,v;
            cin>>t1>>t2>>v;
            AddEdge(t1,t2,v);
            AddEdge(t2,t1,v);
        }
        int root=1;
        dfs(root,-1,0);
        RMQ_ST();
        for(int i=1;i<=Q;i++)
        {
            int u1,u2;
            cin>>u1>>u2;
            int u=query(u1,u2);
            cout<<dep[First[u1]]+dep[First[u2]]-2*dep[First[u]]<<endl;
        }
    }
}