This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define dbg(...)
#define STRUCT_DBG(...)
#else
#include "lib/debug.h"
#endif
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
using vll = vector<ll>;
using vpll = vector<pair<ll, ll>>;
using vvll = vector<vector<ll>>;
using vvpll = vector<vector<pair<ll, ll>>>;
template <class T>
using indexed_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define RFOR(i, e, s) for (ll i = (ll)e - 1; i >= (ll)s; i--)
#define TRAV(a, c) for (const auto &a : c)
#define all(x) x.begin(), x.end()
#define MOD 1000000007
// #define MOD 998244353
#define FASTIO
#define PRECISION
// #define FILE "file"
#define SINGLE
// #define MULTIPLE
// #define GOOGLE
void solve() {
ll n, m, q;
cin >> n >> m >> q;
vvll graph(n + 1);
FOR(i, 0, n - 1) {
ll a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vll euler, dist, tin(n + 1), level(n + 1);
ll cdist = 0;
function<void(ll, ll)> dfs1 = [&](ll curr, ll prev) {
tin[curr] = euler.size();
level[curr] = cdist;
euler.push_back(curr);
dist.push_back(cdist);
cdist++;
TRAV(e, graph[curr]) {
if (e == prev) continue;
dfs1(e, curr);
euler.push_back(curr);
dist.push_back(cdist - 1);
}
cdist--;
};
dfs1(1, 0);
ll L = 20;
vvpll st(L, vpll(euler.size()));
FOR(i, 0, euler.size()) st[0][i] = {dist[i], euler[i]};
FOR(i, 1, L) {
CFOR(j, 0, euler.size() - (1ll << i)) {
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1ll << (i - 1))]);
}
}
auto lca = [&](ll x, ll y) {
x = tin[x];
y = tin[y];
if (x > y) swap(x, y);
ll q = 63 - __builtin_clzll(y - x + 1);
return min(st[q][x], st[q][y - (1ll << q) + 1]).second;
};
auto ds = [&](ll x, ll y) {
return level[x] + level[y] - 2 * level[lca(x, y)];
};
vll c(m + 1);
CFOR(i, 1, m) cin >> c[i];
FOR(_, 0, q) {
ll l, r;
cin >> l >> r;
vll nodes;
nodes.reserve(r - l + 2);
ll root = c[l];
CFOR(i, l, r) {
nodes.push_back(c[i]);
root = lca(root, c[i]);
}
nodes.push_back(root);
sort(all(nodes));
nodes.erase(unique(all(nodes)), nodes.end());
sort(all(nodes), [&](ll o1, ll o2) { return tin[o1] < tin[o2]; });
vll stk = {root};
ll ans = 1;
for (auto it = nodes.begin() + 1; it != nodes.end(); it++) {
vll tr;
while (lca(stk.back(), *it) != stk.back()) {
tr.push_back(stk.back());
stk.pop_back();
}
if (tr.size() && stk.back() != lca(*it, tr.back())) {
stk.push_back(lca(*it, tr.back()));
}
FOR(i, 0, tr.size() - 1) {
ans += ds(tr[i], tr[i + 1]);
}
if (tr.size()) ans += ds(tr.back(), stk.back());
stk.push_back(*it);
}
FOR(i, 0, stk.size() - 1) {
ans += ds(stk[i], stk[i + 1]);
}
cout << ans << "\n";
// vll cc;
// cc.reserve(edges.size() * 2);
// TRAV(e, edges) {
// cc.push_back(e.first);
// cc.push_back(e.second);
// }
// sort(all(cc));
// cc.erase(unique(all(cc)), cc.end());
// vvpll cgraph(cc.size());
// ll ans = 0;
// TRAV(e, edges) {
// ll u = lower_bound(all(cc), e.first) - cc.begin();
// ll v = lower_bound(all(cc), e.second) - cc.begin();
// ll d = ds(e.first, e.second);
// cgraph[u].push_back({v, d});
// cgraph[v].push_back({u, d});
// ans += d - 1;
// }
// function<pll(ll, ll)> dfs2 = [&](ll curr, ll prev) -> pll {
// pll best = {0, curr};
// TRAV(e, cgraph[curr]) {
// if (e.first == prev) continue;
// pll obj = dfs2(e.first, curr);
// obj.first += e.second;
// best = max(best, obj);
// }
// return best;
// };
// pll o1 = dfs2(0, -1);
// pll o2 = dfs2(o1.second, -1);
// cout << ans - o2.first << "\n";
// cout << ans + cc.size() << "\n";
}
}
int main() {
#ifdef FASTIO
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#endif
#ifdef PRECISION
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
#endif
#ifdef FILE
freopen((FILE + string(".in")).c_str(), "r", stdin);
freopen((FILE + string(".out")).c_str(), "w", stdout);
#endif
#ifdef SINGLE
solve();
#endif
#ifdef MULTIPLE
ll t;
cin >> t;
for (ll i = 1; i <= t; i++) {
solve();
}
#endif
#ifdef GOOGLE
ll t;
cin >> t;
for (ll i = 1; i <= t; i++) {
cout << "Case #" << i << ": ";
solve();
}
#endif
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |