题目链接：SPOJ 913

给定一棵 $n$ 个节点的树，第 $i$ 条边有边权 $c_i$，需要支持如下 $2$ 种操作：

• DIST a b：询问点 $a$ 和 $b$ 之间的边权和。
• KTH a b k：询问点 $a$ 到 $b$ 的有向路径的第 $k$ 个点的标号。

询问以 DONE 结束。

本题有 $T$ 组数据。

数据范围：$1\le T\le 25$，$1\le n\le 10 ^ 4$，$1\le c_i\le 10 ^ 5$。

Solution

这题还是直接将边化为点，主要问题是 KTH 操作：由于边变成了点，因此我们要查询的是 $a$ 和 $b$ 组成的 $\text{Splay}$ 中的第 $2k - 1$ 个点。直接套用 $\text{Splay}$ 中的 kth 函数即可。

时间复杂度：$\mathcal O(T \cdot n\log n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 2e4 + 5;

int n;

struct Node;
Node *null;

struct Node {
    Node *ch[2], *fa;
    int val, sz, sum, idx;
    bool rev;
    Node() {
        ch[0] = ch[1] = fa = null;
        val = sz = sum = idx = rev = 0;
    }
    bool get() {
        return fa->ch[1] == this;
    }
    bool isroot() {
        return fa->ch[0] != this && fa->ch[1] != this;
    }
    void reverse() {
        rev ^= 1, std::swap(ch[0], ch[1]);
    }
    void pushup() {
        sz = ch[0]->sz + ch[1]->sz + 1;
        sum = ch[0]->sum + ch[1]->sum + val;
    }
    void pushdown() {
        if (rev) {
            ch[0]->reverse();
            ch[1]->reverse();
            rev = 0;
        }
    }
} *a[N];

struct LCT {
    LCT() {
        null = new Node();
        null->ch[0] = null->ch[1] = null->fa = null;
        null->sz = 0;
    }
    void build(int n) {
        for (int i = 1; i <= n; i++) {
            a[i] = new Node();
        }
    }
    void clear(int n) {
        delete null;
        for (int i = 1; i <= n; i++) {
            delete a[i];
        }
    }
    void pushtag(Node *x) {
        if (!x->isroot()) pushtag(x->fa);
        x->pushdown();
    }
    void rotate(Node *x) {
        Node *y = x->fa, *z = y->fa;
        int k = x->get();
        !y->isroot() && (z->ch[y->get()] = x), x->fa = z;
        y->ch[k] = x->ch[!k], x->ch[!k]->fa = y;
        x->ch[!k] = y, y->fa = x;
        y->pushup();
    }
    void splay(Node *x) {
        pushtag(x);
        while (!x->isroot()) {
            Node *y = x->fa;
            if (!y->isroot()) {
                rotate(x->get() == y->get() ? y : x);
            }
            rotate(x);
        }
        x->pushup();
    }
    Node *kth(Node *rt, int k) {
        Node *u = rt;
        while (1) {
            u->pushdown();
            if (k <= u->ch[0]->sz) {
                u = u->ch[0];
            } else if (k > u->ch[0]->sz + 1) {
                k -= u->ch[0]->sz + 1;
                u = u->ch[1];
            } else {
                return u;
            }
        }
    }
    void access(Node *x) {
        for (Node *y = null; x != null; x = (y = x)->fa) {
            splay(x), x->ch[1] = y, x->pushup();
        }
    }
    void makeroot(Node *x) {
        access(x), splay(x), x->reverse();
    }
    void split(Node *x, Node *y) {
        makeroot(x), access(y), splay(y);
    }
    void link(Node *x, Node *y) {
        makeroot(x);
        x->fa = y;
    }
};

int main() {
    int T;
    for (scanf("%d", &T); T--; ) {
        scanf("%d", &n);
        LCT T;
        T.build(n + n - 1);
        for (int i = 1; i <= n; i++) {
            a[i]->idx = i;
        }
        for (int i = 1; i < n; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            a[i + n]->val = w;
            T.link(a[u], a[i + n]);
            T.link(a[v], a[i + n]);
        }
        while (1) {
            char s[10];
            scanf("%s", s + 1);
            if (s[2] == 'O') break;
            if (s[1] == 'D') {
                int u, v;
                scanf("%d%d", &u, &v);
                T.split(a[u], a[v]);
                printf("%d\n", a[v]->sum);
            } else {
                int u, v, k;
                scanf("%d%d%d", &u, &v, &k);
                T.split(a[u], a[v]);
                printf("%d\n", T.kth(a[v], k + k - 1)->idx);
            }
        }
        T.clear(n + n - 1);
    }
    return 0;
}