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 <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
int N, R, Q, SQRT_N;
const int MAX_N = 2e5 + 1;
const int MX_SQRT = 448;
const int MAX_R = 25001;
vector<int> graph[MAX_N], rgraph[MAX_N];
int sol[MX_SQRT][MAX_R];
int regions[MAX_N], reg_cnt[MAX_R], conv[MAX_R], tin[MAX_N], tout[MAX_N], cnt[MAX_R];
vector<int> sqrt_r;
void dfs(int v)
{
for (int r : sqrt_r)
sol[conv[r]][regions[v]] += cnt[conv[r]];
cnt[regions[v]]++;
for (int u : graph[v])
dfs(u);
cnt[regions[v]]--;
}
void etour(int v, int &tim)
{
tin[v] = tim++;
rgraph[regions[v]].push_back(tin[v]);
for (int u : graph[v])
etour(u, tim);
tout[v] = tim++;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> R >> Q;
SQRT_N = sqrt(N);
cin >> regions[0];
--regions[0];
reg_cnt[regions[0]]++;
for (int i = 1; i < N; i++)
{
int v;
cin >> v >> regions[i];
--regions[i];
--v;
graph[v].push_back(i);
reg_cnt[regions[i]]++;
}
for (int i = 0; i < R; i++)
{
if (reg_cnt[i] >= SQRT_N)
{
sqrt_r.push_back(i);
conv[i] = sqrt_r.size() - 1;
}
else
conv[i] = -1;
}
int tim = 0;
etour(0, tim);
dfs(0);
for (int _ = 0; _ < Q; _++)
{
int a, b;
cin >> a >> b;
--a;
--b;
if (conv[a] != -1)
{
cout << sol[conv[a]][b] << endl;
continue;
}
int res = 0;
for (int v : rgraph[a])
{
if (rgraph[b].empty())
continue;
res += lower_bound(rgraph[b].begin(), rgraph[b].end(), tout[v]) - lower_bound(rgraph[b].begin(), rgraph[b].end(), tin[v]);
}
cout << res << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |