导了一整天了,实在导不出来了,有没有人帮我导一下
查看原帖
导了一整天了,实在导不出来了,有没有人帮我导一下
938212
OMG_NOIP楼主2024/1/7 16:17

导了一整天了,实在导不出来了,有没有人帮我导一下 WA on test 71,有没有大佬帮我 导 调一下求求了QWQ

#include<bits/stdc++.h>
#define ll long long
#define MAXN 1000005
using namespace std;
vector<ll>eg[MAXN];
vector<pair<ll,ll> >q[MAXN];
ll dep[MAXN],size[MAXN],son[MAXN];
void dfs1(ll fa,ll p){
    size[p]=1;
    dep[p]=dep[fa]+1;
    for(ll v:eg[p]){
        if(v==fa)continue;
        dfs1(p,v);
        size[p]+=size[v];
        if(size[son[p]]<size[v])son[p]=v;
    }
}
ll n,m,ans[MAXN];
map<string,ll>mp[MAXN];
string name[MAXN];
void add(ll fa,ll p,ll S){
    mp[dep[p]][name[p]]++;
    for(ll v:eg[p]){
        if(v==fa||v==S)continue;
        add(p,v,S);
    }
}
void del(ll fa,ll p){
    mp[dep[p]][name[p]]--;
    if(mp[dep[p]][name[p]]==0)mp[dep[p]].erase(name[p]);
    for(ll v:eg[p]){
        if(v==fa)continue;
        del(p,v);
    }
}
void dfs2(ll fa,ll p,ll opt){
    for(ll v:eg[p]){
        if(v==fa||v==son[p])continue;
        dfs2(p,v,0);
    }
    if(son[p])dfs2(p,son[p],1);
    add(fa,p,son[p]);
    for(pair<ll,ll> it:q[p]){
        ans[it.first]=mp[dep[p]+it.second].size();
    }
    if(!opt)del(fa,p);
}
ll adx,adk;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0); 
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>name[i]>>adk;
        if(adk!=0){
            eg[i].push_back(adk);
            eg[adk].push_back(i);
        }
    }
    cin>>m;
    for(ll i=1;i<=m;i++){
        cin>>adx>>adk;
        q[adx].push_back({i,adk});
    }
    for(ll i=1;i<=n;i++){
        if(!dep[i]){
            dfs1(0,i);
            dfs2(0,i,0);
        }
    }
    for(ll i=1;i<=m;i++)cout<<ans[i]<<endl;
    return 0;
}
2024/1/7 16:17
加载中...