SPOJ 913. Query on a tree II

SPOJ Problem Set (classical) SPOJ 913. Query on a tree II Problem code: QTREE2
 
 
You are given a tree (an undirected acyclic connected graph) with N nodes, and edges numbered 1, 2, 3...N-1. Each edge has an integer value assigned to it, representing its length.
We will ask you to perfrom some instructions of the following form:

DIST a b : ask for the distance between node a and node bor

KTH a b k : ask for the k-th node on the path from node a to node b

Example:N = 6 1 2 1//edge connects node 1 and node 2 has cost 1 2 4 1 2 5 2 1 3 1 3 6 2 Path from node 4 to node 6 is 4 -> 2 -> 1 -> 3 -> 6 DIST 4 6 : answer is 5 (1 + 1 + 1 + 2 = 5) KTH 4 6 4 : answer is 3 (the 4-th node on the path from node 4 to node 6 is 3) 
Input
The first line of input contains an integer t, the number of test cases (t <= 25). t test cases follow.
For each test case:

In the first line there is an integer N (N <= 10000)

In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 100000)

The next lines contain instructions "DIST a b" or "KTH a b k"

The end of each test case is signified by the string "DONE".

There is one blank line between successive tests.
Output
For each "DIST" or "KTH" operation, write one integer representing its result.
Print one blank line after each test.
Example

Input:

1



6

1 2 1

2 4 1

2 5 2

1 3 1

3 6 2

DIST 4 6

KTH 4 6 4

DONE



Output:

5

3
-------------------------------------------------------------------
    ：         ，     ，DIST(i,j)    i j       ，KTH(i,j,k)    i j     k      。
    ：            。          2^i   。  DIST  ，        lca，        。  KTH  ，   lca，          lca           lca    。     ，        ，RE  。

#include <stdio.h>

#include <string.h>

#include <vector>

#define clr(a,b) memset(a,b,sizeof(a))

using namespace std;



const int N=200005;

int n,eid;

int head[N],ed[N<<1],val[N<<1],nxt[N<<1];

vector<int>fa[N];

int sta[N],top,dep[N],dis[N];



void addedge(int s,int e,int v){

    ed[eid]=e;val[eid]=v;nxt[eid]=head[s];head[s]=eid++;

}



void dfs(int s,int f,int d,int ds){

    fa[s].clear();int k=1;dep[s]=d;dis[s]=ds;

    while(top-k>=0){

        fa[s].push_back(sta[top-k]);k*=2;

    }

    sta[top++]=s;

    for(int i=head[s];~i;i=nxt[i]){

        int e=ed[i],v=val[i];

        if(e!=f)dfs(e,s,d+1,ds+v);

    }

    top--;

}



int lca(int a,int b){

    if(a==b)return a;

    if(dep[b]>dep[a])swap(a,b);

    while(dep[a]>dep[b]){

        int len=fa[a].size(),le=0,ri=len,mid;

        while(mid=(le+ri)>>1,ri>le){

            if(dep[fa[a][mid]]>=dep[b])le=mid+1;

            else ri=mid;

        }

        a=fa[a][ri-1];

    }

    if(a==b)return a;

    while(1){

        int len=fa[a].size(),le=0,ri=len,mid;

        while(mid=(le+ri)>>1,ri>le){

            if(fa[a][mid]!=fa[b][mid])le=mid+1;

            else ri=mid;

        }

        if(ri==0)return fa[a][ri];

        a=fa[a][ri-1];b=fa[b][ri-1];

    }

    return a;

}



int kth(int a,int b,int k){

    int r=lca(a,b);

    if(dep[a]-dep[r]+1>=k){

        int u=dep[a]-k+1;

        while(1){

            if(u==dep[a])return a;

            int len=fa[a].size(),le=0,ri=len,mid;

            while(mid=(le+ri)>>1,ri>le){

                if(dep[fa[a][mid]]>=u)le=mid+1;

                else ri=mid;

            }

            a=fa[a][ri-1];

        }

    }

    else{

        int u=k-dep[a]+dep[r]*2-1;

        while(1){

            if(u==dep[b])return b;

            int len=fa[b].size(),le=0,ri=len,mid;

            while(mid=(le+ri)>>1,ri>le){

                if(dep[fa[b][mid]]>=u)le=mid+1;

                else ri=mid;

            }

            b=fa[b][ri-1];

        }

    }

}



int main(){

//    freopen("/home/axorb/in","r",stdin);

    int T;scanf("%d",&T);

    while(T--){

        eid=0;clr(head,-1);scanf("%d",&n);

        for(int i=1;i<n;i++){

            int a,b,c;scanf("%d%d%d",&a,&b,&c);

            addedge(a,b,c);addedge(b,a,c);

        }

        top=0;dfs(1,-1,1,0);

//        for(int i=1;i<=n;i++)printf("%d %d %d
",i,fa[i].size(),dep[i]);

        char ss[20];

        while(scanf("%s",ss),ss[1]!='O')

            if(ss[1]=='I'){

                int a,b;scanf("%d%d",&a,&b);

                int r=lca(a,b);

                printf("%d
",dis[a]+dis[b]-2*dis[r]);

            }

            else{

                int a,b,c;scanf("%d%d%d",&a,&b,&c);

                printf("%d
",kth(a,b,c));

            }

        puts("");

    }

}