QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#756093#6958. EquivalenceharlemML 0ms0kbC++141.4kb2024-11-16 19:01:012024-11-16 19:01:02

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 19:01:02]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-11-16 19:01:01]
  • 提交

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=1;i<n;i++)ed[i].clear();
    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;
}

詳細信息

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...

output:


result: