Submission #878241

#TimeUsernameProblemLanguageResultExecution timeMemory
878241TAhmed33Tourism (JOI23_tourism)C++98
0 / 100
5088 ms94036 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 25;
int in[MAXN], out[MAXN], depth[MAXN];
pair <int, int> sparse[__lg(MAXN)][MAXN];
int sparse2[__lg(MAXN)][MAXN];

vector <int> adj[MAXN];
int n, m, q;
int cnt = 0;
void dfs (int pos, int par, int dep = 1) {
	depth[pos] = dep;
	sparse[0][++cnt] = {dep, pos};
	assert(cnt < MAXN);
	in[pos] = cnt;
	for (auto j : adj[pos]) {
		if (j != par) {
			dfs(j, pos, dep + 1);
			sparse[0][++cnt] = {dep, pos};
			assert(cnt < MAXN);
		}
	}
	out[pos] = dep;
}
int query (int l, int r) {
	if (l > r) swap(l, r);
	if (l == r) return sparse[0][l].second;
	int x = __lg(r - l + 1);
	return min(sparse[x][l], sparse[x][r - (1 << x) + 1]).second;
}
int query2 (int l, int r) {
    int x = __lg(r - l + 1);
    return query(in[sparse2[x][l]], in[sparse2[x][r - (1 << x) + 1]]);
}
int arr[MAXN];
int main () {
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, -1);
	for (int i = 1; i <= __lg(cnt); i++) {
		for (int j = 1; j <= cnt; j++) {
			sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + (1 << (i - 1))]);
		}
	}
    for (int i = 1; i <= m; i++) {
        cin >> arr[i];
        sparse2[0][i] = arr[i];
    }
    for (int i = 1; i <= __lg(m); i++) {
        for (int j = 1; j + (1 << i) - 1 <= m; j++) {
            sparse2[i][j] = query(in[sparse2[i - 1][j]], in[sparse2[i - 1][j + (1 << (i - 1))]]);
        }
    }
    for (int i = 1; i <= m; i++) {
        int lca = arr[i];
        for (int j = i; j <= m; j++) {
            lca = query(in[lca], in[arr[j]]);
            assert(lca == query2(i, j));
        }
    }
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		vector <int> g;
		for (int j = l; j <= r; j++) g.push_back(arr[j]);
		sort(g.begin(), g.end(), [&] (int a, int b) {
			return in[a] < in[b];
		});
		int ans = depth[g[0]];
		for (int j = 1; j < (int)g.size(); j++) {
			ans += depth[g[j]] - depth[query(in[g[j]], in[g[j - 1]])];
		}
		cout << ans - query2(l, r) + 1 << '\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...