这篇题解 在查询 $v$ 在 $u$ 的哪一个子树中（代码中的 check(u, v)）使用的是暴力遍历所有出边的方法，复杂度显然是 $O(qn)$ 的。

数据生成器：

int n = 1e5;
cout << n << " " << n << " " << n - 1 << "\n";
for(int i = 2; i <= n - 3; i ++)
    cout << 1 << " " << i << "\n";
cout << n - 3 << " " << n - 2 << "\n";
cout << n - 2 << " " << n - 1 << "\n";
cout << n - 1 << " " << n - 0 << "\n";
cout << n - 0 << " " << n - 3 << "\n";
for(int i = 2; i <= n; i ++)
    cout << 1 << " " << i << "\n";

本机需要 ~2.6s。