【spoj】【QTREE2 - Query on a tree II】

題目大意

給出一棵樹，每條邊有邊權，詢問兩點之間的距離，以及從起點到終點第k個點是那個點。

解題思路

觀察可知，整個詢問是靜态的，可以使用倍增算法解決。

code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define Min(a,b) ((a<b)?a:b)
#define Max(a,b) ((a>b)?a:b)
#define Fo(i,j,k) for(int i=j;i<=k;i++)
#define Fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int const MxN=e4;
int N,M,Edge,Mx,Two[],Begin[MxN+],Dep[MxN+],Fa[MxN+][],Dis[MxN+][],To[MxN*2+],Len[MxN*2+],Next[MxN*2+];
void Insert(int U,int V,int W){
    To[++Edge]=V;
    Len[Edge]=W;
    Next[Edge]=Begin[U];
    Begin[U]=Edge;
}
void Dfs(int Now,int Pre){
    Dep[Now]=Dep[Pre]+;
    for(int i=Begin[Now];i;i=Next[i])if(To[i]!=Pre)Fa[To[i]][]=Now,Dis[To[i]][]=Len[i],Dfs(To[i],Now);
}
int Lc(int U,int V,int &Ans){
    if(Dep[U]<Dep[V])swap(U,V);
    Fd(i,Mx,)if(Dep[Fa[U][i]]>=Dep[V])Ans+=Dis[U][i],U=Fa[U][i];
    if(U==V)return U;
    Fd(i,Mx,)if(Fa[U][i]!=Fa[V][i])Ans+=Dis[U][i]+Dis[V][i],U=Fa[U][i],V=Fa[V][i];
    Ans+=Dis[U][]+Dis[V][];return Fa[U][];
}
int Up(int U,int V){
    Fd(i,Mx,)if(Two[i]<=V)V-=Two[i],U=Fa[U][i];
    return U;
}
int main(){
    //freopen("d.in","r",stdin);
    //freopen("d.out","w",stdout);
    Two[]=;Fo(i,,)Two[i]=Two[i-]<<;
    int T;scanf("%d",&T);
    Fo(cas,,T){
    scanf("%d",&N);Mx=log(N)/log();
    Edge=;Fo(i,,N)Begin[i]=;
    int U,V,W;
    Fo(i,,N){
        scanf("%d%d%d\n",&U,&V,&W);
        Insert(U,V,W);Insert(V,U,W);
    }
    Dfs(,);int Lca;char Ch;
    Fo(j,,Mx)Fo(i,,N)Fa[i][j]=Fa[Fa[i][j-]][j-],Dis[i][j]=Dis[i][j-]+Dis[Fa[i][j-]][j-];
    while(){
        Ch=getchar();
        if(Ch=='D'){
            Ch=getchar();
            if(Ch=='I'){
                scanf("ST%d%d\n",&U,&V);
                int Ans=;Lc(U,V,Ans);
                printf("%d\n",Ans);
            }else{scanf("NE\n\n");break;}

        }else{
            scanf("TH%d%d%d\n",&U,&V,&W);
            int Ans,Lca=Lc(U,V,Ans);
            if(Dep[U]-Dep[Lca]+>=W)printf("%d\n",Up(U,W-));
            else printf("%d\n",Up(V,Dep[U]+Dep[V]-Dep[Lca]*2+-W));
        }
    }
    printf("\n");
    }
    return ;
}