| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1107613 | abczz | Tourism (JOI23_tourism) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#define ll long long
using namespace std;
vector <ll> adj[100000];
vector <array<ll, 2>> Q[100000];
ll bl[100000][18];
ll n, m, q, a, b, cnt, sz[100000], A[100000], D[100000], G[100000], pos[100000], X[100000];
vector <ll> V[100000];
ll tot = 0;
struct BIT{
ll st[100050];
void build(){
memset(st, 0, sizeof(st));
}
void update(ll id, ll w) {
if (!id) return;
tot += w;
for (; id<100050; id+=id&-id) st[id] += w;
}
ll query(ll id) {
ll ret = 0;
for (; id; id-=id&-id) ret += st[id];
return ret;
}
}bit;
struct MPSegment{
map <ll, array<ll, 2>> mp;
vector <ll> lazy;
void init(ll sz) {
mp[0] = {sz-1, -1};
}
void update(ll id, ll l, ll r, ll w) {
auto it = mp.lower_bound(l);
if (it != mp.begin()) {
it = prev(it);
bit.update(it->second[1]+1, -(it->second[0]-(l-1)));
mp[it->first] = {l-1, it->second[1]};
}
it = mp.lower_bound(l);
while (it != mp.end()) {
auto nx = next(it);
if (it->first > r) break;
if (it->second[0] <= r) {
bit.update(it->second[1]+1, -(it->second[0]-it->first+1));
mp.erase(it);
}
else {
bit.update(it->second[1]+1, -(r+1-it->first));
mp[r+1] = {it->second[0], it->second[1]};
mp.erase(it);
break;
}
it = nx;
}
mp[l] = {r, w};
bit.update(w+1, r-l+1);
}
}ST[100000];
ll lca(ll a, ll b) {
if (a == -1) return b;
else if (b == -1) return a;
if (D[a] > D[b]) swap(a, b);
ll db = D[b];
for (int j=17; j>=0; --j) {
if (db-(1LL<<j) >= D[a]) {
db -= (1LL<<j);
b = bl[b][j];
}
}
for (int j=17; j>=0; --j) {
if (bl[a][j] != bl[b][j]) {
a = bl[a][j], b = bl[b][j];
}
}
if (a != b) return bl[a][0];
else return a;
}
struct LCATree{
ll st[400000];
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = lca(A[l], A[l+1]);
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = lca(st[id*2], st[id*2+1]);
}
ll query(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql) return -1;
else if (ql <= l && r <= qr) return st[id];
ll mid = (l+r)/2;
return lca(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
}
}LCAST;
void dfs(ll u, ll p) {
sz[u] = 1;
for (auto v : adj[u]) {
if (v == p) continue;
D[v] = D[u] + 1;
bl[v][0] = u;
sz[u] += sz[v];
dfs(v, u);
}
}
void hld(ll u, ll p, ll k) {
G[u] = k, pos[u] = V[k].size();
V[k].push_back(u);
ll mx = -1, id = -1;
for (auto v : adj[u]) {
if (v == p) continue;
if (sz[v] > mx) mx = sz[v], id = v;
}
if (id != -1) hld(id, u, k);
for (auto v : adj[u]) {
if (v == p || v == id) continue;
X[cnt+1] = u;
hld(v, u, ++cnt);
}
}
void jump(ll u, ll v, ll w) {
if (G[u] == G[v]) {
if (pos[v] == pos[u]) return;
ST[G[u]].update(1, pos[v], pos[u], w);
return;
}
ST[G[u]].update(1, 0, pos[u], w);
jump(X[G[u]], v, w);
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
cin >> n >> m >> q;
bit.build();
for (int i=0; i<n-1; ++i) {
cin >> a >> b;
--a, --b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(0, -1);
hld(0, -1, 0);
for (int j=1; j<18; ++j) {
for (int i=0; i<n; ++i) {
bl[i][j] = bl[bl[i][j-1]][j-1];
}
}
for (int i=0; i<=cnt; ++i) {
ST[i].init(V[i].size());
}
vector <ll> F(q, 0);
for (int i=0; i<m; ++i) {
cin >> A[i];
--A[i];
}
if (m > 1) LCAST.build(1, 0, m-2);
for (int i=0; i<q; ++i) {
cin >> a >> b;
--a, --b;
Q[b].push_back({a, i});
}
for (int i=0; i<m; ++i) {
jump(A[i], 0, i);
for (auto [x, y] : Q[i]) {
if (x == i) {
F[y] = 1;
continue;
}
F[y] = tot - bit.query(x) - (m == 1 ? 0 : D[LCAST.query(1, 0, m-2, x, i-1)]);
//cout << tot << " " << bit.query(x) << endl;
}
}
for (int i=0; i<q; ++i) cout << F[i] << '\n';
}