$des$
一棵 $n$ 个点的树，树上有 $m$ 条双向的公交线路，每条公交线路都在
两个节点之间沿最短路径往返。
$q$ 次询问从一个点要到达另一个点，在只坐公交的情况下，至少需
要坐几辆公交车；或者判断无法只坐公交到达。
$n,m,q <= 2 \times 10^5$
$sol$
对于每个点，先预处理出从这个点坐一次公交车能最远到达哪个
祖先。对于一条公交线路 (u,v)，将 lca 的信息挂在 u,v 上，dfs 一遍向上
更新信息即可。
通过倍增算出从某个点坐 $2^k$ 次最远能到达哪个祖先。这样对于一
条路径 (u,v)，我们就能快速算出 u,v 走到 lca 分别至少需要多少辆车，
假设答案分别为 $a,b$，那么询问的答案要么是 $a + b$，要么是 $a + b - 1$
。判断的方法也很简单，先算出 $u$ 向上坐 $a - 1$ 次，$v$ 向上坐 $b - 1$
次，最远能到达哪个节点。若存在一条线路经过这两个节点，则答案
为 $a + b - 1$。也就是判断是否有一条线路的两端分别在这两个节点的
子树中。
这可以变成了一个二维数点问题，时间复杂度 $O((n + m + q)logn)$，不会
$O(nlog^2n)$ 卡过
问题转化为树上存在 $n$ 对点对，每对点对带有不同的权值 a，每次询问点对
$(x, y)$ 二者的子树内是否存在相同的点的权值
可以用线段树套set维护
$code$
#include <bits/stdc++.h> using namespace std; #define gc getchar()
inline int read() {
int x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x;
} #define E exit(0)
#define Rep(i, a, b) for(int i = a; i <= b; i ++) const int N = 2e5 + ; int fa[N], size[N], topp[N], son[N], deep[N] = {( << )}, lst[N], rst[N], sptime;
int f[N][];
int upst[N]; vector <int> G[N]; int n; void Dfs_1(int u, int f_, int dep) {
fa[u] = f_, deep[u] = dep, size[u] = ;
int S = G[u].size();
Rep(i, , S - ) {
int v = G[u][i];
if(v == f_) continue;
Dfs_1(v, u, dep + );
if(size[v] > size[son[u]]) son[u] = v;
}
} void Dfs_2(int u, int tp) {
topp[u] = tp; lst[u] = ++ sptime;
if(!son[u]) {
rst[u] = sptime; return ;
}
Dfs_2(son[u], tp);
int S = G[u].size();
Rep(i, , S - ) {
int v = G[u][i];
if(v != fa[u] && v != son[u]) Dfs_2(v, v);
}
rst[u] = sptime;
} inline int Lca(int x, int y) {
int tpx = topp[x], tpy = topp[y];
while(tpx != tpy) {
if(deep[tpx] < deep[tpy]) swap(x, y), swap(tpx, tpy);
x = fa[tpx], tpx = topp[x];
}
if(x == y) return x;
if(deep[x] < deep[y]) swap(x, y);
return y;
} void Dfs_3(int u) {
int S = G[u].size();
Rep(i, , S - ) {
int v = G[u][i];
if(v == fa[u]) continue;
Dfs_3(v);
if(deep[upst[v]] < deep[upst[u]]) upst[u] = upst[v];
}
} set <int> Tree[N << ]; #define lson jd << 1
#define rson jd << 1 | 1 void Poi_G(int l, int r, int jd, int x, int num) {
if(Tree[jd].count(num) == ) Tree[jd].insert(num);
if(l == r) return ;
int mid = (l + r) >> ;
if(x <= mid) Poi_G(l, mid, lson, x, num);
else Poi_G(mid + , r, rson, x, num);
} bool flag; set <int> :: iterator wl, wr; void Sec_A(int l, int r, int jd, int x, int y, int fl, int fr) {
if(flag || Tree[jd].size() == ) return ;
if(x <= l && r <= y) {
if(Tree[jd].count(fl) || Tree[jd].count(fr)) {
flag = ; return ;
}
Tree[jd].insert(fr);
wl = Tree[jd].lower_bound(fl);
wr = Tree[jd].lower_bound(fr);
Tree[jd].erase(fr);
if(wr == wl) return ;
if(wr != wl) flag = ;
return ;
}
int mid = (l + r) >> ;
if(x <= mid && flag == ) Sec_A(l, mid, lson, x, y, fl, fr);
if(y > mid && flag == ) Sec_A(mid + , r, rson, x, y, fl, fr);
} inline void Calc(int x, int y) {
int ret;
int lca = Lca(x, y);
int a = , b = , lstx = x, lsty = y, tmpx = x, tmpy = y;
for(int i = ; i >= ; i --) {
if(deep[f[x][i]] > deep[lca]) a += ( << i), x = f[x][i];
}
for(int i = ; i >= ; i --) {
if(deep[f[y][i]] > deep[lca]) b += ( << i), y = f[y][i];
}
if(deep[f[x][]] > deep[lca] || deep[f[y][]] > deep[lca]) {
puts("-1"); return ;
}
flag = ;
int l1 = lst[x], r1 = rst[x], l2 = lst[y], r2 = rst[y];
Sec_A(, n, , l1, r1, l2, r2); Sec_A(, n, , l2, r2, l1, r1);
if(lca == x || lca == y) ret = a + b + ;
else if(flag == ) ret = a + b + ;
else ret = a + b + ;
printf("%d\n", ret);
} int main() {
n = read(); Rep(i, , n) {
int u = read();
G[u].push_back(i), G[i].push_back(u);
} Dfs_1(, , );
Dfs_2(, ); int m = read();
Rep(i, , m) {
int u = read(), v = read();
int lca = Lca(u, v);
if(deep[lca] < deep[upst[u]] || upst[u] == ) upst[u] = lca;
if(deep[lca] < deep[upst[v]] || upst[v] == ) upst[v] = lca;
Poi_G(, n, , lst[u], lst[v]);
} Dfs_3();
Rep(i, , n) f[i][] = upst[i];
Rep(i, , ) {
Rep(j, , n) f[j][i] = f[f[j][i - ]][i - ];
} m = read();
Rep(i, , m) {
int a = read(), b = read();
Calc(a, b);
}
return ;
}