QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#756087 | #6958. Equivalence | harlem | ML | 0ms | 0kb | C++14 | 1.3kb | 2024-11-16 18:59:38 | 2024-11-16 18:59:38 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,T=20;
int n;
int f[N][T+1];
int v[N];
vector<int> ed[N];
int dp[N];
int cf[N];
int ans;
void dfsi(int now){
dp[now]=dp[f[now][0]]+1;
for(auto nxt:ed[now]){
dfsi(nxt);
}
}
void binit(){
for(int t=1;t<=T;t++){
for(int i=1;i<=n;i++){
f[i][t]=f[f[i][t-1]][t-1];
}
}
}
int lca(int a,int b){
if(dp[a]>dp[b])swap(a,b);
for(int t=T;t>=0;t--){
if(dp[f[b][t]]>=dp[a])b=f[b][t];
}
if(a==b)return a;
for(int t=T;t>=0;t--){
if(f[a][t]!=f[b][t]){
a=f[a][t];
b=f[b][t];
}
}
return a;
}
void dfss(int now){
for(auto nxt:ed[now]){
dfss(nxt);
cf[now]+=cf[nxt];
if(cf[nxt]>1&&v[nxt]!=0)ans++;
}
}
void solve(){
cin>>n;
f[1][0]=1;
for(int i=2;i<=n;i++)cin>>f[i][0];
for(int i=2;i<=n;i++){
cin>>v[i];
ed[f[i][0]].push_back(i);
}
dfsi(1);
binit();
for(int i=2,j;i<=n;i++){
cin>>j;
int k=lca(i,j);
cf[k]-=2;
cf[i]++;cf[j]++;
}
ans=0;
dfss(1);
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
8514 265000 72963 99588 118133 209949 249723 133275 171942 167920 86420 191069 169911 123458 176051 140795 122013 123039 252726 229192 52056 65706 247786 155474 231748 50060 24682 114313 43549 53896 73048 149564 51333 62885 117376 255302 235170 95044 56347 246767 193580 219540 227757 92735 173157 17...