#include<bits/stdc++.h>
#define ll int
#define f(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
// #define mod 998244353
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(int i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (int)1e9
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
// ll binpow(ll a, ll b, ll md){ll res=1;a%=mod;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
using namespace std;
const int N=512;
ll n,r,q,tt=1;
vector<vector<ll> > v;
vector<vector<pair<ll,ll> > > reg;
vector<ll> st,en,euler,region;
void dfs(int cur, int par)
{
st[cur]=tt++,euler.pb(region[cur]);
f(i,0,sz(v[cur]))
{
ll node=v[cur][i];
if(node!=par)
dfs(node,cur);
}
en[cur]=tt-1;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("xortransform.in","r",stdin);
// freopen("xortransform.out","w",stdout);
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
int z=1;
// cin>>z;
f(i,1,z+1)
{
//cout<<"Case #"<<i<<": ";
cin>>n>>r>>q;
v.rz(n+1),st.rz(n+1),en.rz(n+1),reg.rz(r+1),region.rz(n+1);
cin>>region[1];
reg[region[1]].pb({1,0});
f(i,2,n+1)
{
ll num;
cin>>num>>region[i];
v[i].pb(num),v[num].pb(i),reg[region[i]].pb({i,0});
}
euler.pb(0);
dfs(1,1);
f(i,1,r+1)
{
f(j,0,sz(reg[i]))
reg[i][j]=mp(st[reg[i][j].ff],en[reg[i][j].ff]);
sort(all(reg[i]));
}
euler.pb(0);
map<pair<ll,ll>,ll> val;
f(i,1,r+1)
{
if(sz(reg[i])>N)
{
vector<ll> tot(tt+2);
f(j,0,sz(reg[i]))
tot[reg[i][j].ff]++,tot[reg[i][j].ss+1]--;
f(j,1,tt+1)
{
tot[j]+=tot[j-1];
val[{i,euler[j]}]+=tot[j];
}
}
}
while(q--)
{
ll r1,r2;
cin>>r1>>r2;
if(sz(reg[r1])>N)
cout<<val[{r1,r2}]<<endl;
else
{
ll ans=0;
f(i,0,sz(reg[r1]))
ans+=(ub(all(reg[r2]),mp(reg[r1][i].ss,inf))-lb(all(reg[r2]),mp(reg[r1][i].ff,-1)));
cout<<ans<<endl;
}
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
1 ms |
208 KB |
Output is correct |
3 |
Correct |
1 ms |
208 KB |
Output is correct |
4 |
Correct |
6 ms |
208 KB |
Output is correct |
5 |
Correct |
7 ms |
336 KB |
Output is correct |
6 |
Correct |
16 ms |
336 KB |
Output is correct |
7 |
Correct |
26 ms |
464 KB |
Output is correct |
8 |
Correct |
19 ms |
464 KB |
Output is correct |
9 |
Correct |
41 ms |
976 KB |
Output is correct |
10 |
Correct |
59 ms |
1232 KB |
Output is correct |
11 |
Correct |
60 ms |
1652 KB |
Output is correct |
12 |
Correct |
126 ms |
2392 KB |
Output is correct |
13 |
Correct |
189 ms |
2492 KB |
Output is correct |
14 |
Correct |
243 ms |
2996 KB |
Output is correct |
15 |
Correct |
241 ms |
6292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1577 ms |
7732 KB |
Output is correct |
2 |
Correct |
2023 ms |
7508 KB |
Output is correct |
3 |
Correct |
2581 ms |
10224 KB |
Output is correct |
4 |
Correct |
215 ms |
3200 KB |
Output is correct |
5 |
Correct |
230 ms |
5204 KB |
Output is correct |
6 |
Correct |
1347 ms |
5220 KB |
Output is correct |
7 |
Correct |
1297 ms |
7092 KB |
Output is correct |
8 |
Correct |
1052 ms |
13168 KB |
Output is correct |
9 |
Correct |
1964 ms |
15028 KB |
Output is correct |
10 |
Correct |
3713 ms |
20764 KB |
Output is correct |
11 |
Correct |
3719 ms |
18240 KB |
Output is correct |
12 |
Correct |
1174 ms |
18864 KB |
Output is correct |
13 |
Correct |
1697 ms |
19884 KB |
Output is correct |
14 |
Correct |
2281 ms |
42028 KB |
Output is correct |
15 |
Correct |
2759 ms |
25580 KB |
Output is correct |
16 |
Correct |
2890 ms |
32872 KB |
Output is correct |
17 |
Correct |
3391 ms |
53328 KB |
Output is correct |