Algorithm
problem link- https://www.spoj.com/problems/QTREE2/
QTREE2 - Query on a tree II
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 perform some instructions of the following form:
- DIST a b : ask for the distance between node a and node b
or - 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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 1e4+5;
const int LG = log2(MAXN) + 1;
int n;
vector<pair<int, int> > adj[MAXN];
int level[MAXN], par[MAXN][LG], cost[MAXN];
void dfs(int u, int parent, int c){
cost[u] = cost[parent] + c;
level[u] = level[parent] + 1;
par[u][0] = parent;
for(auto v : adj[u]){
if(v.first == parent) continue;
dfs(v.first, u, v.second);
}
}
int lca(int u, int v){
if(level[u] < level[v]) swap(u, v);
int log = log2(level[u]);
for(int i = log; i >= 0; i--)
if(level[u]-level[v] >= (1 << i))
u = par[u][i];
if(u == v)
return u;
for(int i = log; i >= 0; i--){
if(par[u][i] != -1 && par[u][i] != par[v][i]){
u = par[u][i];
v = par[v][i];
}
}
return par[u][0];
}
int kth(int n, int k){
int log = log2(level[n]);
for(int i = 0; i <= log; i++){
if(k & (1 << i))
n = par[n][i];
}
return n;
}
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i = 1;i <= n; i++){
adj[i].clear();
level[i] = 0;
}
for(int i = 0;i < n-1; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
memset(par, -1, sizeof par);
level[0] = -1;
dfs(1, 0, 0);
for(int j = 1; j < LG; j++){
for(int i = 1; i <= n; i++){
if(par[i][j-1] != -1)
par[i][j] = par[par[i][j-1]][j-1];
}
}
char query[8];
while(scanf("%s", query) == 1){
if(query[1] == 'O') break;
int a, b;
scanf("%d%d", &a, &b);
if(query[1] == 'I'){
int lc = lca(a, b);
int ans = cost[a] + cost[b] - 2*cost[lc];
printf("%d\n", ans);
}else{
int k;
scanf("%d", &k);
int lc = lca(a, b);
int left = level[a]-level[lc]+1;
if(k <= left)
printf("%d\n", kth(a, k-1));
else
printf("%d\n", kth(b, (level[b]-level[lc])-(k-left)));
}
}
printf("\n");
}
return 0;
}Input
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
3
Demonstration
SPOJ Solution-Query on a tree II-Solution in C, C++, Java, Python