1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
struct Node {
int x, y, val, op, idx;
} node[MAXN << 4];
int node_idx;
bool cmp(Node a, Node b) {
if (a.x != b.x) return a.x < b.x;
if (a.y != b.y) return a.y < b.y;
return a.op < b.op;
}
int n, m, q;
int c[MAXN];
void modify(int p, int val) {
for (; p <= n; p += p & (-p))
c[p] += val;
}
int query(int p) {
int ret = 0;
for (; p; p -= p & (-p))
ret += c[p];
return ret;
}
vector<int> G[MAXN];
int f[MAXN][18], dep[MAXN], dfn[MAXN], siz[MAXN], dfn_idx;
void dfs(int u, int fa) {
f[u][0] = fa, dep[u] = dep[fa] + 1, dfn[u] = ++dfn_idx, siz[u] = 1;
for (int i = 1; i <= 17; ++i)
f[u][i] = f[f[u][i - 1]][i - 1];
for (vector<int>::iterator it = G[u].begin(); it != G[u].end(); it++) {
int v = *it;
if (v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
}
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = 17; i >= 0; --i)
if (dep[f[u][i]] >= dep[v]) u = f[u][i];
if (u == v) return u;
for (int i = 17; i >= 0; --i)
if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
return f[u][0];
}
int jump(int u, int d) {
int k = 0;
while (d) {
if (d & 1) u = f[u][k];
k++;
d >>= 1;
}
return u;
}
int ans[MAXN];
int main() {
freopen("mirror.in", "r", stdin);
freopen("mirror.out", "w", stdout);
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i < n; ++i) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
int t = lca(u, v);
if (t == u || t == v) {
if (dep[u] < dep[v]) swap(u, v);
int w = jump(u, dep[u] - dep[v] - 1);
node[++node_idx] = (Node) {dfn[u], 1, 1, 0, 0};
node[++node_idx] = (Node) {dfn[u], dfn[w], -1, 0, 0};
node[++node_idx] = (Node) {dfn[u], dfn[w] + siz[w], 1, 0, 0};
node[++node_idx] = (Node) {dfn[u] + siz[u], 1, -1, 0, 0};
node[++node_idx] = (Node) {dfn[u] + siz[u], dfn[w], 1, 0, 0};
node[++node_idx] = (Node) {dfn[u] + siz[u], dfn[w] + siz[w], -1, 0, 0};
} else {
node[++node_idx] = (Node) {dfn[u], dfn[v], 1, 0, 0};
node[++node_idx] = (Node) {dfn[u], dfn[v] + siz[v], -1, 0, 0};
node[++node_idx] = (Node) {dfn[u] + siz[u], dfn[v], -1, 0, 0};
node[++node_idx] = (Node) {dfn[u] + siz[u], dfn[v] + siz[v], 1, 0, 0};
}
}
for (int i = 1; i <= q; ++i) {
int u, v;
scanf("%d%d", &u, &v);
node[++node_idx] = (Node) {dfn[u], dfn[v], 0, 1, i};
node[++node_idx] = (Node) {dfn[v], dfn[u], 0, 1, i};
}
sort(node + 1, node + node_idx + 1, cmp);
for (int i = 1; i <= node_idx; ++i) {
if (node[i].op == 1) {
ans[node[i].idx] += query(node[i].y);
} else {
modify(node[i].y, node[i].val);
}
}
for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
return 0;
}
|