分析
显然大树最多会有 $10^{10}$ 个点，完全开不下。
但是发现每次操作都是复制一颗子树，所以可以把大树当做一颗树套树。
构造大树时，令每一个大节点为模板树中的一颗子树，并对大树重新编号，就像这样：
作出如下定义：
- 两个大节点的边权为对应的树的根节点的距离，比如上图$1$和$2$之间的边权为$2$。
- $st[i]$ 表示大节点 $i$ 对应的小节点的编号区间的起点，如 $st[1]=1$，$st[2]=6$。
- $ed[i]$ 表示大节点 $i$ 对应的小节点的编号区间的终点，如 $ed[1]=5$，$ed[2]=8$。
- $pre[i]$ 表示大节点 $i$ 对应的是模板树中哪一个节点的子树，如 $pre[1]=1$，$pre[2]=4$。
- $lnk[i]$ 表示大节点 $i$ 挂在哪一个节点下面，如$lnk[2]=3$，$lnk[3]=2$。
这些信息都很容易求出。
再定义如下函数：
- $get\_root(x)$ ：查找小节点 $x$ 所在的大节点。因为 $st$ 是递增的，所以只要二分就可以确定。
- $get\_pre(x)$：查找小节点 $x$ 在模板树中对应的节点。假设 $x$ 在大节点 $y$ 中，我们只要找到 $y$ 对应的树中第 $x-st[y]+1$ 小的节点即可。这个可以用主席树实现。
现在来考虑怎么算答案。
主要思想是，先跳到大节点对应的子树的根节点，再在大树上跳到同一个大节点内，再在该大节点对应的子树内跳到同一个小节点，然后沿途累加距离。
这个过程和求 LCA 非常像，然而细节比较多，写代码时要注意。
代码
放个格式化后的代码。
// It is made by M_sea
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define re register
typedef long long ll;
using namespace std;
inline ll read() {
ll X = 0;
int w = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
return X * w;
}
const int N = 100000 + 10;
struct president_tree {
struct node {
int lc, rc, sum;
};
node t[N * 20];
int rt[N], tot;
president_tree() { this->tot = 0; }
inline int build(int l, int r) {
int p = ++tot;
t[p].sum = 0;
if (l == r) return p;
int mid = (l + r) >> 1;
t[p].lc = build(l, mid), t[p].rc = build(mid + 1, r);
return p;
}
inline int insert(int now, int l, int r, int x) {
int p = ++tot;
t[p] = t[now], ++t[p].sum;
if (l == r) return p;
int mid = (l + r) >> 1;
if (x <= mid)
t[p].lc = insert(t[p].lc, l, mid, x);
else
t[p].rc = insert(t[p].rc, mid + 1, r, x);
t[p].sum = t[t[p].lc].sum + t[t[p].rc].sum;
return p;
}
inline int query(int p, int q, int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1;
int dlt = t[t[q].lc].sum - t[t[p].lc].sum;
if (k <= dlt)
return query(t[p].lc, t[q].lc, l, mid, k);
else
return query(t[p].rc, t[q].rc, mid + 1, r, k - dlt);
}
} T;
namespace template_tree {
struct Edge {
int v, nxt;
} e[N << 1];
int head[N], cnt = 0;
inline void addEdge(int u, int v) {
e[++cnt] = (Edge){v, head[u]}, head[u] = cnt;
}
int n, dfs_clock = 0;
int f[20][N], dep[N], st[N], ed[N], pos[N], sz[N];
inline void dfs(int u, int fa) {
dep[u] = dep[fa] + 1, f[0][u] = fa, st[u] = ++dfs_clock,
pos[dfs_clock] = u;
for (re int i = 1; i <= 16; ++i) f[i][u] = f[i - 1][f[i - 1][u]];
for (re int i = head[u]; i; i = e[i].nxt)
if (e[i].v != fa) dfs(e[i].v, u);
ed[u] = dfs_clock, sz[u] = ed[u] - st[u] + 1;
}
inline void build_president_tree() {
T.rt[0] = T.build(1, n);
for (re int i = 1; i <= n; ++i)
T.rt[i] = T.insert(T.rt[i - 1], 1, n, pos[i]);
}
inline void build() {
for (re int i = 1; i < n; ++i) {
int u = read(), v = read();
addEdge(u, v), addEdge(v, u);
}
dfs(1, 0);
build_president_tree();
}
inline int get_lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (re int i = 16; i >= 0; i--)
if (dep[f[i][u]] > dep[v]) u = f[i][u];
if (dep[u] != dep[v]) u = f[0][u];
for (re int i = 16; i >= 0; i--)
if (f[i][u] != f[i][v]) u = f[i][u], v = f[i][v];
if (u != v) u = f[0][u], v = f[0][v];
return u;
}
inline int get_dis(int u, int v) {
int w = get_lca(u, v);
return dep[u] + dep[v] - 2 * dep[w];
}
} // namespace template_tree
namespace big_tree {
int n, m;
ll tot;
int f[20][N], dep[N], pre[N];
ll dis[20][N], st[N], ed[N], lnk[N];
inline int get_root(ll u) {
int L = 1, R = n;
while (L <= R) {
int mid = (L + R) >> 1;
if (st[mid] <= u)
L = mid + 1;
else
R = mid - 1;
}
return R;
}
inline int get_pre(ll u) {
int rt = get_root(u);
return T.query(T.rt[template_tree::st[pre[rt]] - 1],
T.rt[template_tree::ed[pre[rt]]], 1, template_tree::n,
u - st[rt] + 1);
}
inline void build() {
n = dep[1] = pre[1] = st[1] = 1, tot = ed[1] = template_tree::n;
for (re int i = 1; i <= m; ++i) {
ll u = read(), v = read();
int rt = get_root(v);
dep[++n] = dep[rt] + 1, lnk[n] = v, pre[n] = u;
st[n] = tot + 1, ed[n] = tot + template_tree::sz[u], tot = ed[n];
f[0][n] = rt, dis[0][n] = template_tree::dep[get_pre(v)] -
template_tree::dep[pre[rt]] + 1;
for (re int j = 1; j <= 16; ++j)
f[j][n] = f[j - 1][f[j - 1][n]],
dis[j][n] = dis[j - 1][n] + dis[j - 1][f[j - 1][n]];
}
}
inline ll calc_ans(ll u, ll v) {
int fu = get_root(u), fv = get_root(v);
if (fu == fv) return template_tree::get_dis(get_pre(u), get_pre(v));
if (dep[fu] < dep[fv]) swap(u, v), swap(fu, fv);
ll ans = template_tree::dep[get_pre(u)] - template_tree::dep[pre[fu]];
u = fu;
for (re int i = 16; i >= 0; --i)
if (dep[f[i][u]] > dep[fv]) ans += dis[i][u], u = f[i][u];
if (get_root(lnk[u]) == fv)
return ans + 1 +
template_tree::get_dis(get_pre(lnk[u]), get_pre(v));
ans += template_tree::dep[get_pre(v)] - template_tree::dep[pre[fv]];
v = fv;
if (dep[u] > dep[v]) ans += dis[0][u], u = f[0][u];
for (re int i = 16; i >= 0; --i)
if (f[i][u] != f[i][v])
ans += dis[i][u] + dis[i][v], u = f[i][u], v = f[i][v];
return ans + 2 +
template_tree::get_dis(get_pre(lnk[u]), get_pre(lnk[v]));
}
} // namespace big_tree
int Q;
int main() {
template_tree::n = read(), big_tree::m = read(), Q = read();
template_tree::build();
big_tree::build();
while (Q--) {
ll u = read(), v = read();
printf("%lld\n", big_tree::calc_ans(u, v));
}
return 0;
}