#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> son1[200000];
vector<int> son2[200000];
int ind1[262144];
int sz1[200000];
int ind2[262144];
int rev2[200000];
int sz2[200000];
int f1=0;
int f2=0;
void dfs1(int v,int prev) {
ind1[v]=f1++;
sz1[v]=1;
for(int nt:son1[v]) {
dfs1(nt,v);
sz1[v]+=sz1[nt];
}
}
void dfs2(int v,int prev) {
ind2[v]=f2++;
rev2[ind2[v]]=v;
sz2[v]=1;
for(int nt:son2[v]) {
dfs2(nt,v);
sz2[v]+=sz2[nt];
}
}
const int sz=262144;
vector<int> v[sz*2];
void init(int node=1,int nodel=0,int noder=sz-1) {
if (nodel==noder) {
if (nodel<n) {
v[node].push_back(ind1[rev2[nodel]]);
}
return;
}
int mid=(nodel+noder)/2;
init(node*2,nodel,mid);
init(node*2+1,mid+1,noder);
int i1=0;
int i2=0;
while (i1<v[node*2].size()||i2<v[node*2+1].size()) {
if (i2==v[node*2+1].size()||(i1<v[node*2].size()&&v[node*2][i1]<v[node*2+1][i2])) {
v[node].push_back(v[node*2][i1++]);
}
else {
v[node].push_back(v[node*2+1][i2++]);
}
}
}
int query(int l,int r,int d,int u) {
int ret=0;
for(int pl=sz;pl>0;pl/=2) {
if (l==r) {
ret+=upper_bound(v[l+pl].begin(),v[l+pl].end(),u)-lower_bound(v[l+pl].begin(),v[l+pl].end(),d);
//printf("%d ",l+pl);
break;
}
if (l%2==1) {
ret+=upper_bound(v[l+pl].begin(),v[l+pl].end(),u)-lower_bound(v[l+pl].begin(),v[l+pl].end(),d);
//printf("%d ",l+pl);
l++;
}
if (r%2==0) {
ret+=upper_bound(v[r+pl].begin(),v[r+pl].end(),u)-lower_bound(v[r+pl].begin(),v[r+pl].end(),d);
//printf("%d ",r+pl);
r--;
}
l/=2;
r/=2;
}
//printf("\n");
return ret;
}
int main(void) {
scanf("%d",&n);
for(int i=1;i<n;i++) {
int p;
scanf("%d",&p);
p--;
son1[p].push_back(i);
}
for(int i=1;i<n;i++) {
int p;
scanf("%d",&p);
p--;
son2[p].push_back(i);
}
dfs1(0,-1);
dfs2(0,-1);
init();
for(int i=0;i<n;i++) {
printf("%d ",query(ind2[i],ind2[i]+sz2[i]-1,ind1[i],ind1[i]+sz1[i]-1)-1);
}
}
Compilation message
Main.cpp: In function 'void init(int, int, int)':
Main.cpp:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | while (i1<v[node*2].size()||i2<v[node*2+1].size()) {
| ~~^~~~~~~~~~~~~~~~~
Main.cpp:49:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | while (i1<v[node*2].size()||i2<v[node*2+1].size()) {
| ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | if (i2==v[node*2+1].size()||(i1<v[node*2].size()&&v[node*2][i1]<v[node*2+1][i2])) {
| ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:50:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | if (i2==v[node*2+1].size()||(i1<v[node*2].size()&&v[node*2][i1]<v[node*2+1][i2])) {
| ~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
Main.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%d",&p);
| ~~~~~^~~~~~~~~
Main.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d",&p);
| ~~~~~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
18 ms |
22084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
18 ms |
22084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
