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>
#define endl '\n'
#define int ll
using namespace std;
int N, R, Q, SQRT_N;
vector<vector<int>> graph, sol, rgraph;
vector<int> regions, reg_cnt, sqrt_r, conv, tin, tout;
vector<int> cnt;
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)
{
rgraph[regions[v]].push_back(v);
tin[v] = tim++;
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);
graph = vector<vector<int>>(N);
regions = vector<int>(N, -1);
reg_cnt = vector<int>(R, 0);
conv = vector<int>(R, -1);
cnt = vector<int>(R, 0);
tin = vector<int>(N);
tout = vector<int>(N);
rgraph = vector<vector<int>>(R);
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;
}
sol = vector<vector<int>>(sqrt_r.size(), vector<int>(R, 0));
int tim = 0;
etour(0, tim);
dfs(0);
while (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;
int l = 0, r = rgraph[b].size() - 1;
int lb = -1;
while (l <= r)
{
int m = l + (r - l) / 2;
int u = rgraph[b][m];
if (tin[u] < tin[v])
l = m + 1;
else if (tout[u] > tout[v])
r = m - 1;
else
{
lb = m;
r = m - 1;
}
}
if (lb == -1)
continue;
l = 0;
r = rgraph[b].size() - 1;
int rb = -1;
while (l <= r)
{
int m = l + (r - l) / 2;
int u = rgraph[b][m];
if (tin[u] < tin[v])
l = m + 1;
else if (tout[u] > tout[v])
r = m - 1;
else
{
rb = m;
l = m + 1;
}
}
res += (rb - lb + 1);
}
cout << res << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |