#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
const int MAXN = 1 << 18;
const int MAXK = 20;
int n, m, q;
vector<pair<int, int>> graf[MAXN];
bool pomczy[MAXN];
int skok[MAXN][MAXK];
int depth[MAXN];
int pot2[MAXK];
int gleb[MAXN];
int preorder[MAXN];
int postorder[MAXN];
int seg[2 * MAXN];
pair<int, int> gdzie[MAXN];
pair<int, int> policz[MAXN];
int odp[MAXN];
int C[MAXN];
bool pierw = true;
int kt = 1;
int kt2 = 1;
struct pytaj {
int l, r, nr, typ;
};
vector<pytaj> dodaj;
void upd(int v, int x) {
v += MAXN;
while (v > 0) {
seg[v] += x;
v /= 2;
}
}
int query(int l, int r) {
l += MAXN;
r += MAXN;
int ans = 0;
while (l < r) {
if ((l % 2) == 1) {
ans += seg[l];
l++;
}
if ((r % 2) == 0) {
ans += seg[r];
r--;
}
l /= 2;
r /= 2;
}
if (l == r) {
ans += seg[l];
}
return ans;
}
void dfs(int v, int last, int dl) {
// cout << "last = " << last << " v = " << v << " dl = " << dl << '\n';
policz[v] = gdzie[v];
depth[v] = depth[last] + dl;
if (pierw) {
gleb[v] = gleb[last] + 1;
skok[v][0] = last;
for (int k = 1; k < MAXK; k++) {
skok[v][k] = skok[skok[v][k - 1]][k - 1];
}
preorder[v] = kt;
kt++;
}
for (auto syn: graf[v]) {
if (syn.st == last) continue;
dfs(syn.st, v, syn.nd);
policz[v].st = max(policz[v].st, policz[syn.st].st);
policz[v].nd = min(policz[v].nd, policz[syn.st].nd);
}
if (v != last) {
dodaj.pb({policz[v].st, policz[v].nd, dl, 0});
}
// cout << "w = " << v << " policz = " << policz[v].st << " " << policz[v].nd << " dl = " << dl << '\n';
if (pierw) {
postorder[v] = kt2;
kt2++;
}
if (v == last) {
pierw = false;
kt = 1;
kt2 = 1;
}
}
int lca(int a, int b) {
if (gleb[a] > gleb[b]) {
swap(a, b);
}
int k = MAXK - 1;
while (gleb[b] > gleb[a]) {
if ((gleb[b] - pot2[k]) >= gleb[a]) {
b = skok[b][k];
}
k--;
}
if (a == b) {
return a;
}
k = MAXK - 1;
while (skok[a][0] != skok[b][0]) {
if (skok[a][k] != skok[b][k]) {
a = skok[a][k];
b = skok[b][k];
}
k--;
}
return skok[a][0];
}
void znajdz(int l, int r, int sr) {
for (int i = l; i < sr; i++) {
gdzie[C[i]].st = i;
}
for (int i = r; i > sr; i--) {
gdzie[C[i]].nd = i;
}
}
void prepot2() {
pot2[0] = 1;
for (int k = 1; k < MAXK; k++) {
pot2[k] = pot2[k - 1] * 2;
}
}
bool por1(int a, int b) {
return preorder[a] < preorder[b];
}
void stworznowe(vector<int> &vec) {
sort(vec.begin(), vec.end(), por1);
for (auto x: vec) {
pomczy[x] = true;
}
int sz = vec.size();
rep(i, sz - 1) {
int v = lca(vec[i], vec[i + 1]);
// cout << "lca = " << v << " a = " << vec[i] << " b = " << vec[i + 1] << endl;
if (pomczy[v]) continue;
pomczy[v] = true;
vec.pb(v);
}
for (auto v: vec) {
pomczy[v] = false;
}
sort(vec.begin(), vec.end(), por1);
int last = vec[0];
sz = vec.size();
int ojc[sz];
ojc[last] = last;
for (int i = 1; i < sz; i++) {
int v = vec[i];
// cout << "last = " << last << " v = " << v << endl;
while (postorder[v] > postorder[last]) {
last = ojc[last];
}
// cout << "KONIEC" << endl;
// cout << "tworzysz = " << " v = " << v << " last = " << last << " gl v = " << gleb[v] << " gl last = " << gleb[last] << '\n';
graf[v].pb({last, gleb[v] - gleb[last]});
graf[last].pb({v, gleb[v] - gleb[last]});
ojc[v] = last;
last = v;
}
}
vector<pytaj> pyt;
bool por2(pytaj a, pytaj b) {
pair<int, int> a2 = {a.r, a.typ};
pair<int, int> b2 = {b.r, b.typ};
return (a2 < b2);
}
void rob(int l, int r) {
dodaj.clear();
// cout << "l = " << l << " r = " << r << endl;
if (l == r) {
for (auto p: pyt) {
odp[p.nr] = 0;
}
return ;
}
int sr = (l + r)/2;
vector<pytaj> pom1;
vector<pytaj> pom2;
vector<pytaj> ter;
// cout << "CH1" << endl;
for (auto p: pyt) {
if (p.l <= sr && p.r >= sr) {
ter.pb(p);
}
else if (p.r < sr) {
pom1.pb(p);
}
else {
pom2.pb(p);
}
}
// cout << "CH2" << endl;
pyt.clear();
vector<int> vec;
for (int i = l; i <= r; i++) {
int v = C[i];
// cout << "i = " << i << " v = " << v << endl;
if (pomczy[v]) continue;
pomczy[v] = true;
vec.pb(v);
}
// cout << "CH3" << endl;
stworznowe(vec);
// cout << "CH4" << endl;
for (auto v: vec) {
gdzie[v] = {-1, m + 1};
policz[v] = {-1, m + 1};
}
znajdz(l, r, sr);
// for (auto v: vec) {
// cout << "v = " << v << " l = " << gdzie[v].st << " r = " << gdzie[v].nd << '\n';
// }
// cout << "CH5" << endl;
int w = C[sr];
// cout << "w = " << w << endl;
depth[w] = 0;
// cout << "START" << endl;
// for (auto v: vec) {
// cout << "v = " << v << " l = " << gdzie[v].st << " r = " << gdzie[v].nd << '\n';
// }
dfs(w, w, 0);
// for (auto v: vec) {
// cout << "v = " << v << " l = " << policz[v].st << " r = " << policz[v].nd << '\n';
// }
// cout << "XD" << endl;
for (auto p: dodaj) {
ter.pb(p);
// cout << "L = " << p.l << " R = " << p.r << " liczba = " << p.nr << endl;
}
// cout << "CH6" << endl;
sort(ter.begin(), ter.end(), por2);
for (auto p: ter) {
if (p.typ == 0) {
if (p.l >= 0) {
upd(p.l, p.nr);
}
}
}
// cout << "CH7" << endl;
int pomoc = 0;
for (auto p: ter) {
if (p.typ == 0) {
if (p.l >= 0) {
upd(p.l, -p.nr);
}
pomoc += p.nr;
}
else {
// cout << "PYYYYTAAAAAANIEEEE = " << p.l << " " << p.r << '\n';
int ile = query(p.l, sr);
odp[p.nr] = pomoc + ile;
}
}
// cout << "CH8" << endl;
ter.clear();
for (auto v: vec) {
graf[v].clear();
}
vec.clear();
pyt.clear();
for (auto p: pom1) {
pyt.pb(p);
}
pom1.clear();
rob(l, sr);
pyt.clear();
for (auto p: pom2) {
pyt.pb(p);
}
rob(sr + 1, r);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
prepot2();
cin >> n >> m >> q;
rep(i, n - 1) {
int a, b;
cin >> a >> b;
graf[a].pb({b, 1});
graf[b].pb({a, 1});
}
dfs(1, 1, 0);
for (int v = 1; v <= n; v++) {
graf[v].clear();
}
rep(i, m) {
cin >> C[i];
}
rep(i, q) {
int l, r;
cin >> l >> r;
l--;
r--;
pyt.pb({l, r, i, 1});
}
// for (auto p: pyt) {
// cout << p.l << " " << p.r << '\n';
// }
rob(0, m - 1);
rep(i, q) {
odp[i]++;
cout << odp[i] << '\n';
}
return 0;
}
# | 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... |