#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const int M = (1 << 17);
// segment Sum + update in pos
int segSum[2 * M];
void update(int pos, int val) {
for(segSum[pos += M] += val; pos > 1; pos >>= 1) {
segSum[pos >> 1] = segSum[pos] + segSum[pos ^ 1];
}
}
int get(int ql, int qr) {
int res = 0;
for(ql += M, qr += M + 1; ql < qr; ql >>= 1, qr >>= 1) {
if(ql & 1) res += segSum[ql++];
if(qr & 1) res += segSum[--qr];
}
return res;
}
template<typename T>
struct SprarseTable {
int len;
vector<vector<T>> st;
T (*F) (T, T);
void init(vector<T> &a, T (*f)(T, T)) {
F = f;
len = (int)a.size();
int mxpw = 32 - __builtin_clz(len);
st.resize(mxpw);
st[0] = a;
for(int k = 1; k < mxpw; k++) {
st[k].resize(len - (1 << k) + 1);
for(int i = 0; i < (int)st[k].size(); i++) {
st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
}
}
}
T get(int l, int r) {
assert(0 <= l && r < len);
int mxpw = 31 - __builtin_clz(len);
return F(st[mxpw][l], st[mxpw][r - (1 << mxpw) + 1]);
}
};
int n, m, q;
vector<int> g[N];
vector<pair<int, int>> e;
int sm[N];
int tin[N], tout[N], anc[N][17], depth[N], T;
void calc(int s, int p) {
if(s == 1) T = 0;
tin[s] = T++;
anc[s][0] = p;
for(int i = 1; i < 17; i++)
anc[s][i] = anc[anc[s][i - 1]][i - 1];
for(int to : g[s]) {
if(to == p) continue;
depth[to] = depth[s] + 1;
calc(to, s);
sm[s] += sm[to];
}
tout[s] = T++;
}
struct query {
int l, r, i;
};
int curAns;
void add(int ver) {
int u = ver;
for(int i = 16; i >= 0; i--) {
if(!get(tin[ anc[u][i] ], tout[ anc[u][i] ]))
u = anc[u][i];
}
curAns += depth[ver] - depth[u] + 1;
update(tin[ver], +1);
}
void del(int ver) {
update(tin[ver], -1);
int u = ver;
for(int i = 16; i >= 0; i--) {
if(!get(tin[ anc[u][i] ], tout[ anc[u][i] ]))
u = anc[u][i];
}
curAns -= depth[ver] - depth[u] + 1;
}
vector<query> qr;
int ans[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m >> q;
for(int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
e.push_back({u, v});
}
vector<int> ver(m + 1);
for(int i = 1; i <= m; i++)
cin >> ver[i];
calc(1, 1);
if(n <= 2000) {
while(q --> 0) {
int l, r;
cin >> l >> r;
for(int i = l; i <= r; i++)
sm[ver[i]] = 1;
calc(1, 1);
int res = 1;
for(int i = 1; i <= n; i++) {
res += (sm[i] && sm[i] < sm[1]);
sm[i] = 0;
}
cout << res << '\n';
}
return 0;
}
bool subtask = 1;
for(int i = 0; i < n - 1; i++) {
if(e[i].first != i + 1 || e[i].second != i + 2)
subtask = 0;
}
if(subtask) {
vector<int> ti(m + 1);
for(int i = 1; i <= m; i++)
ti[i] = tin[ver[i]];
SprarseTable<int> mn, mx;
mn.init(ti, [](int a, int b) {return (a < b ? a : b);});
mx.init(ti, [](int a, int b) {return (a > b ? a : b);});
while(q --> 0) {
int l, r;
cin >> l >> r;
cout << mx.get(l, r) - mn.get(l, r) + 1 << '\n';
}
return 0;
}
for(int i = 0; i < q; i++) {
query c;
cin >> c.l >> c.r; c.i = i;
qr.push_back(c);
}
sort(qr.begin(), qr.end(), [](query a, query b) {return (a.l < b.l)});
int curL = 0, curR = 0;
for(query c : qr) {
while(curR < c.r) {
add(ver[++curR]);
}
while(curL < c.l) {
del(ver[curL++]);
}
ans[c.i] = curAns;
}
for(int i = 0; i < q; i++)
cout << ans[i] << '\n';
}
Compilation message
tourism.cpp: In lambda function:
tourism.cpp:153:72: error: expected ';' before '}' token
153 | sort(qr.begin(), qr.end(), [](query a, query b) {return (a.l < b.l)});
| ^
| ;
tourism.cpp: In instantiation of 'void SprarseTable<T>::init(std::vector<_Tp>&, T (*)(T, T)) [with T = int]':
tourism.cpp:139:63: required from here
tourism.cpp:38:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
38 | st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
| ~~^~~
