Submission #1214147

#TimeUsernameProblemLanguageResultExecution timeMemory
1214147siewjhTourism (JOI23_tourism)C++20
28 / 100
5094 ms25400 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int p[18][MAXN], d[MAXN], ord[MAXN], rord[MAXN], sps[18][MAXN], ans[MAXN], oid = 0, clca, lid, rid, val;
vector<int> adj[MAXN];
multiset<int> sord;
void dfs(int x, int par, int dep){
	p[0][x] = par; d[x] = dep; ord[x] = ++oid; rord[oid] = x;
	for (int nn : adj[x]){
		if (nn == par) continue;
		dfs(nn, x, dep + 1);
	}
}
int lca(int a, int b){
	if (d[a] > d[b]) swap(a, b);
	for (int k = 17; k >= 0; k--)
		if (d[b] - (1 << k) >= d[a])
			b = p[k][b];
	if (a == b) return a;
	for (int k = 17; k >= 0; k--)
		if (p[k][a] != p[k][b]){
			a = p[k][a]; b = p[k][b];
		}
	return p[0][a];
}
int query(int l, int r){
	int k = log2(r - l + 1);
	return lca(sps[k][l], sps[k][r - (1 << k) + 1]);
}
void add(int x){
	auto it = sord.lower_bound(ord[x]);
	int lcad = -1;
	if (it != sord.end()) lcad = max(lcad, d[lca(x, rord[*it])]);
	if (it != sord.begin()) lcad = max(lcad, d[lca(x, rord[*prev(it)])]);
	sord.insert(ord[x]);
	val += d[x] - lcad;
	int nlca = query(lid, rid);
	if (nlca != clca){
		val += d[clca] - d[nlca];
		clca = nlca;
	}
}
void rem(int x){
	sord.erase(sord.find(ord[x]));
	auto it = sord.lower_bound(ord[x]);
	int lcad = -1;
	if (it != sord.end()) lcad = max(lcad, d[lca(x, rord[*it])]);
	if (it != sord.begin()) lcad = max(lcad, d[lca(x, rord[*prev(it)])]);
	val -= d[x] - lcad;
	int nlca = query(lid, rid);
	if (nlca != clca){
		val -= d[nlca] - d[clca];
		clca = nlca;
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int nodes, spots, queries; cin >> nodes >> spots >> queries;
	for (int i = 1; i < nodes; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	dfs(1, -1, 0);
	for (int k = 1; k <= 17; k++)
		for (int i = 1; i <= nodes; i++){
			if (p[k - 1][i] == -1) p[k][i] = -1;
			else p[k][i] = p[k - 1][p[k - 1][i]];
		}
	vector<int> spv(spots + 1);
	for (int i = 1; i <= spots; i++) cin >> spv[i];
	for (int i = 1; i <= spots; i++) sps[0][i] = spv[i];
	for (int k = 1; k <= 17; k++)
		for (int i = spots - (1 << k) + 1; i >= 1; i--)
			sps[k][i] = lca(sps[k - 1][i], sps[k - 1][i + (1 << (k - 1))]);
	vector<tuple<int, int, int, int>> vq(queries);
	int bsz = 320;
	for (int i = 0; i < queries; i++){
		int l, r; cin >> l >> r;
		vq[i] = {r / bsz, l, r, i};
	}
	sort(vq.begin(), vq.end());
	clca = spv[1]; lid = rid = 1; val = 1;
	sord.insert(ord[spv[1]]);
	for (auto [rb, l, r, id] : vq){
		while (rid < r){
			rid++; add(spv[rid]);
		}
		while (lid > l){
			lid--; add(spv[lid]);
		}
		while (rid > r){
			rid--; rem(spv[rid + 1]);
		}
		while (lid < l){
			lid++; rem(spv[lid - 1]);
		}
		ans[id] = val;
	}
	for (int i = 0; i < queries; i++) cout << ans[i] << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...