| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1213702 | quan606303 | Regions (IOI09_regions) | C++20 | 0 ms | 0 KiB |
/*
* @Author: quan606303
* @Date: 2025-06-06 13:36:55
* @Last Modified by: quan606303
* @Last Modified time: 2025-06-06 14:54:43
*/
/*idea :
merge giua online va offline :
+ THT1 online : voi cac thg co size < sqrt(N) thi ta se dung binarysearch de tinh voi do phuc tap la sqrt(N)*log(N)
+ TH2 offline voi cac thg co size >= sqrt(N) thi ta se co toi da sqrt(N) thang giong vay nen ta se tinh het tat ca cap r1,r2 voi r1 la cac thang co size >= sqrt(N) voi do phuc tap toi da la N* sqrt(N).
tong do phuc tap la N*sqrt(N)+q*sqrt(N)*log(N)
*/
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const int maxn=2e5+7;
const int maxR=25000+7;
const int BLOCK=sqrt(maxn);
vector<int> adj[maxn];
vector<int> child[maxR];
int n,R,q,par[maxn];
map<int,int> mp[maxn];
int tin[maxn],tout[maxn],id=0;
void dfs(int u,int p)
{
tin[u]=++id;
for (auto v:adj[u])
{
if (v==p)continue;
dfs(v,u);
}
tout[u]=id;
}
void dfs_cal(int u,int p,int col,int cnt)
{
mp[col][par[u]]+=cnt;
if (par[u]==col)cnt++;
for (auto v:adj[u])
{
if (v==p)continue;
dfs_cal(v,u,col,cnt);
}
if (par[u]==col)cnt--;
}
vector<int> child_tin[maxR];
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// file("test");
cin>>n>>R>>q;
int tam;
cin>>tam;
par[1]=tam;
child[tam].push_back(1);
for (int i=2;i<=n;i++)
{
int s,h;
cin>>s>>h;
par[i]=h;
child[h].push_back(i);
adj[s].push_back(i);
}
dfs(1,0);
// for (int i=1;i<=n;i++)cout<<i<<" "<<tin[i]<<endl;
// cout<<endl;
for (int i=1;i<=R;i++)if (child[i].size()>=BLOCK)dfs_cal(1,0,i,0);
for (int i=1;i<=R;i++)
{
for (auto j:child[i])child_tin[i].push_back(tin[j]);
sort(child_tin[i].begin(),child_tin[i].end());
}
// for (int i=1;i<=R;i++)
// {
// cout<<i<<" : "<<endl;
// for (auto j:child_tin[i])cout<<j<<" ";
// cout<<endl;
// }
while (q--)
{
int r1,r2;
cin>>r1>>r2;
if (child[r1].size()>=BLOCK)cout<<mp[r1][r2]<<endl;
else
{
int ans=0;
for (auto i:child[r1])
{
ans+=max(0,(upper_bound(child_tin[r2].begin(),child_tin[r2].end(),tout[i])-1-child_tin[r2].begin())-(lower_bound(child_tin[r2].begin(),child_tin[r2].end(),tin[i])-child_tin[r2].begin())+1);
}
cout<<ans<<endl;
}
cout<<flush;
}
return 0;
}