[SPOJ-QTREE2]Query on a tree II 题解
![[SPOJ-QTREE2]Query on a tree II 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180319a.jpg)
题目地址：洛谷：【SP913】QTREE2 – Query on a tree II – 洛谷、SPOJ：SPOJ.com – Problem QTREE2
SPOJ QTREE系列：
- [SPOJ-QTREE]Query on a tree 题解（树链剖分）
- [SPOJ-QTREE2]Query on a tree II 题解（树链剖分）
- [SPOJ-PT07J]Query on a tree III 题解（主席树）
- [SPOJ-QTREE3]Query on a tree again! 题解（树链剖分）
- [SPOJ-QTREE4]Query on a tree IV 题解（点分治/边分治）
- [SPOJ-QTREE5]Query on a tree V 题解（边分治）
- [SPOJ-QTREE6]Query on a tree VI 题解（LCT）
- [SPOJ-QTREE7]Query on a tree VII 题解（LCT）
题目描述
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 b
- KTH a b k : ask for the k-th node on the path from node a to node b
给一棵带边权的树，操作1.询问两点路径长2.求两点有向路径上第k点。
输入输出格式
输入格式：
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.
输出格式：
For each “DIST” or “KTH” operation, write one integer representing its result.
Print one blank line after each test.
输入输出样例
输入样例#1：
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
输出样例#1：
5 3
题解
求和同QTREE：[SPOJ-QTREE]Query on a tree 题解 | KSkun’s Blog。查k点可以考虑算一下LCA到两个儿子的距离，看看这个点在哪条链上，然后再换算成底端往上第几个点，沿重链上跳，利用DFS序算出来即可。
代码
// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
register char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
inline bool isop(char c) {
return c == 'I' || c == 'H' || c == 'O';
}
inline char readop() {
register char c;
while(!isop(c = fgc()));
return c;
}
const int MAXN = 10005;
struct Edge {
int to, w, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;
int T, n, m, ut, vt, wt, kt;
char op;
int w[MAXN], fa[MAXN], siz[MAXN], son[MAXN], dfn[MAXN], ptn[MAXN], top[MAXN], dep[MAXN], cnt;
inline void dfs1(int u) {
siz[u] = 1;
son[u] = 0;
for(register int i = head[u]; i; i = gra[i].nxt) {
register int v = gra[i].to;
if(v == fa[u]) continue;
dep[v] = dep[u] + 1;
fa[v] = u;
w[v] = gra[i].w;
dfs1(v);
siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
inline void dfs2(int u, int tp) {
top[u] = tp;
dfn[u] = ++cnt;
ptn[dfn[u]] = u;
if(son[u]) dfs2(son[u], tp);
for(register int i = head[u]; i; i = gra[i].nxt) {
register int v = gra[i].to;
if(v == son[u] || v == fa[u]) continue;
dfs2(v, v);
}
}
LL sgt[MAXN << 2];
inline void build(int o, int l, int r) {
if(l == r) {
sgt[o] = w[ptn[l]];
return;
}
register int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
build(lch, l, mid);
build(rch, mid + 1, r);
sgt[o] = sgt[lch] + sgt[rch];
}
inline void modify(int o, int l, int r, int x, int v) {
if(l == r) {
sgt[o] = v;
return;
}
register int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
if(x <= mid) modify(lch, l, mid, x, v);
else modify(rch, mid + 1, r, x, v);
sgt[o] = sgt[lch] + sgt[rch];
}
inline LL query(int o, int l, int r, int ll, int rr) {
if(l >= ll && r <= rr) {
return sgt[o];
}
register int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
register LL res = 0;
if(ll <= mid) res += query(lch, l, mid, ll, rr);
if(rr > mid) res += query(rch, mid + 1, r, ll, rr);
return res;
}
inline LL querysum(int u, int v) {
int tu = top[u], tv = top[v];
register LL res = 0;
while(tu != tv) {
if(dep[tu] > dep[tv]) {
std::swap(u, v);
std::swap(tu, tv);
}
res += query(1, 1, n, dfn[tv], dfn[v]);
v = fa[tv];
tv = top[v];
}
if(dep[u] > dep[v]) std::swap(u, v);
if(u != v) res += query(1, 1, n, dfn[u] + 1, dfn[v]);
return res;
}
inline int querylca(int u, int v) {
int tu = top[u], tv = top[v];
while(tu != tv) {
if(dep[tu] > dep[tv]) {
std::swap(u, v);
std::swap(tu, tv);
}
v = fa[tv];
tv = top[v];
}
if(dep[u] > dep[v]) std::swap(u, v);
return u;
}
inline int querykth(int u, int v, int k) {
int lca = querylca(u, v), tu = top[u], tv = top[v];
if(dep[u] - dep[lca] + 1 >= k) {
while(dep[tu] > dep[lca]) {
if(dep[u] - dep[tu] + 1 >= k) break;
k -= dep[u] - dep[tu] + 1;
u = fa[tu];
tu = top[u];
}
return ptn[dfn[u] - k + 1];
} else {
k -= dep[u] - dep[lca] + 1;
k = dep[v] - dep[lca] - k + 1;
while(dep[tv] > dep[lca]) {
if(dep[v] - dep[tv] + 1 >= k) break;
k -= dep[v] - dep[tv] + 1;
v = fa[tv];
tv = top[v];
}
return ptn[dfn[v] - k + 1];
}
}
inline void addedge(int u, int v, int w) {
gra[++tot] = Edge {v, w, head[u]};
head[u] = tot;
}
int main() {
T = readint();
while(T--) {
tot = cnt = 0;
memset(head, 0, sizeof(head));
n = readint();
for(int i = 1; i < n; i++) {
ut = readint(); vt = readint(); wt = readint();
addedge(ut, vt, wt);
addedge(vt, ut, wt);
}
dfs1(1);
dfs2(1, 1);
build(1, 1, n);
for(;;) {
op = readop();
if(op == 'O') break;
ut = readint();
vt = readint();
if(op == 'I') {
printf("%lld\n", querysum(ut, vt));
} else {
kt = readint();
printf("%d\n", querykth(ut, vt, kt));
}
}
printf("\n");
}
return 0;
}
