SPOJ 913 QTREE 시리즈 - Query on a tree II (LCA 배가)

제목 주소: QTREE 2 - Query on a tree II LCA 는 오프라인 과 온라인 RMQ 전환 방법 을 배 워 서 이 문 제 를 풀 었 습 니 다. 그래서 오랫동안 생각 했 지만 어떻게 풀 어야 할 지 생각 하지 못 했 습 니 다.문제 풀이 보면 다 쓰 는 거 야.그래서 배 증 법 을 배 워 서 LCA 를 구 했 더 니 배 증 법 으로 하 는 게 물 문제 라 는 걸 알 게 됐어 요...경 로 를 구 하 는 k 번 째 점 은 k 번 째 부모 노드 로 바 뀔 수 있 지만 배가 법의 원 리 는 바로 부모 노드 에 근거 하기 때문에 이 문 제 는 쉽게 해결 할 수 있다.거 리 를 구하 세 요.관건 은 경로 의 k 번 째 점 을 구 하 는 것 이다. 분명히 이 점 은 u 의 k 번 째 부모 노드 이거 나 v 의 k 번 째 부모 노드 이다. 그래서 먼저 LCA 를 구 해서 u 인지 v 인지 판단 한 다음 에 배증 법 으로 그 점 을 찾 으 면 된다.코드 는 다음 과 같 습 니 다:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL long long
#define PI acos(-1.0)
const int mod=1e7+3;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=10000+10;
int dep[MAXN], dis[MAXN], dp[MAXN][30];
int head[MAXN], cnt, n;
struct node
{
        int u, v, w, next;
}edge[MAXN<<1];
void add(int u, int v, int w)
{
        edge[cnt].v=v;
        edge[cnt].w=w;
        edge[cnt].next=head[u];
        head[u]=cnt++;
}
void dfs(int u, int fa)
{
        for(int i=head[u];i!=-1;i=edge[i].next){
                int v=edge[i].v;
                if(v==fa) continue ;
                dep[v]=dep[u]+1;
                dis[v]=dis[u]+edge[i].w;
                dfs(v,u);
                dp[v][0]=u;
        }
}
struct BZ
{
        int i, j;
        void init()
        {
                for(j=1;(1<<j)<=n;j++){
                        for(i=1;i<=n;i++){
                                if(dp[i][j-1]!=-1)
                                dp[i][j]=dp[dp[i][j-1]][j-1];
                        }
                }
        }
        int Query(int u, int v)
        {
                if(dep[u]<dep[v]) swap(u,v);
                for(i=0;(1<<i)<=dep[u];i++) ;
                i--;
                for(j=i;j>=0;j--){
                        if(dep[u]-(1<<j)>=dep[v])
                                u=dp[u][j];
                }
                if(u==v) return u;
                for(j=i;j>=0;j--){
                        if(dp[u][j]!=dp[v][j]){
                                u=dp[u][j];
                                v=dp[v][j];
                        }
                }
                return dp[u][0];
        }
        int kth(int u, int v, int k)
        {
                int root=Query(u,v), ans;
                if(dep[u]-dep[root]+1>=k){
                        ans=dep[u]-k+1;
                        for(i=0;(1<<i)<=dep[u];i++) ;
                        i--;
                        for(j=i;j>=0;j--){
                                if(dep[u]-(1<<j)>=ans)
                                        u=dp[u][j];
                        }
                        return u;
                }
                else{
                        ans=dep[root]+k-(dep[u]-dep[root]+1);
                        for(i=0;(1<<i)<=dep[v];i++) ;
                        i--;
                        for(j=i;j>=0;j--){
                                if(dep[v]-(1<<j)>=ans)
                                        v=dp[v][j];
                        }
                        return v;
                }
        }
}bz;
void init()
{
        memset(head,-1,sizeof(head));
        memset(dep,0,sizeof(dep));
        memset(dis,0,sizeof(dis));
        memset(dp,-1,sizeof(dp));
        cnt=0;
}
int main()
{
        int T, i, u, v, w, k;
        char s[10];
        scanf("%d",&T);
        while(T--){
                scanf("%d",&n);
                init();
                for(i=1;i<n;i++){
                        scanf("%d%d%d",&u,&v,&w);
                        add(u,v,w);
                        add(v,u,w);
                }
                dfs(1,-1);
                bz.init();
                while(scanf("%s",s)!=EOF&&s[1]!='O'){
                        if(s[1]=='I'){
                                scanf("%d%d",&u,&v);
                                printf("%d
",dis[u]+dis[v]-2*dis[bz.Query(u,v)]);
                        }
                        else{
                                scanf("%d%d%d",&u,&v,&k);
                                printf("%d
",bz.kth(u,v,k));
                        }
                }
        }
        return 0;
}