|
]; ans += Dis[y][i];
x = Fa[x][i], y = Fa[y][i];
}
gx = GetId(md[x].fa).fi, gy = GetId(md[y].fa).fi;
return ans + 2 + GetDis(gx, gy) + calc(prey);
}
signed main() {
//freopen("tree13.in", "r", stdin);freopen("b.out", "w", stdout);
N = read(); M = read() + 1; Q = read();
for(int i = 1; i <= N - 1; i++) {
int x = read(), y = read();
v[x].push_back(y);
v[y].push_back(x);
}
dfs1(1, 0);
dfs2(1, 1);//树剖
for(int i = 1; i <= N; i++) insert(root[i], root[i - 1], 1, N, rev[i]);
md[1] = {1, siz[1], 1, 0, 1};
lin.insert(md[1]);
tot = siz[1] + 1;
for(int i = 2; i <= M; i++) {
int x = read(), to = read();
md[i] = {tot, tot + siz[x] - 1, x, to, i};
lin.insert(md[i]);
tot += siz[x];
}
for(int i = 2; i <= M; i++) {
Ope x = md[i];
int u = x.ti, v = GetId(x.fa).se;//大树以操作次序来标号
V[v].push_back(u);
Dis[u][0] = dep[GetId(md[u].fa).fi] - dep[md[v].id] + 1;
Fa[u][0] = v;
t[u][0] = md[u].fa;
}
Dfs(1, 0);
Pre();
while(Q--) {
LL x = read(), y = read();
cout << Query(x, y) << '\n';
}
return 0;
}
|