E. *【树链剖分】Qtree2 加强版

传统题

1000ms

2048MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $N$ 个点，编号为 $1 \sim N$ ，有 $N-1$ 条边，每条边都有长度。

有若干个操作，操作分为两种

DIST $u$ $v$ ：表示询问 $u$ 到 $v$ 的距离。

KTH $u$ $v$ $k$ ：表示询问从 $u$ 到 $v$ 路径上第 $k$ 个点的编号（保证路径上至少 $k$ 个点）。

第一行输入一个整数 $N$ ，表示有 $N$ 个点（ $1 \le N \le 10^6$ ）

下来 $N-1$ 行每行输入三个整数 $x，y，c$ ，表示点 $x$ 到点 $y$ 有一条长度为 $c$ 的边。

下来若干个操作。读入“DONE”时停止。

操作详情见题目描述。

对于每次操作输出相应答案即可。

5
3