# E

``````// Problem: 最大稳定数值
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/84528/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x) ((x)&(-(x)))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define maxheap(x) priority_queue<x,vector<x>,less<x> >
#define minheap(x) priority_queue<x,vector<x>,greater<x> >
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef long long ll;
typedef unsigned long long ull;
ll val[1000005];
vector<int>es[1000005];
ll pre[100005];
ll suf[100005];
int yes[100005];
int cnt[100005];
int x[100005],y[100005];
void dfs(int x,int pa)
{
pre[x]=pre[pa]+val[x];
suf[x]=val[x];
for(auto i:es[x])
{
if(i==pa)continue;
dfs(i,x);
suf[x]+=suf[i];
}
}
void dfs1(int x,int pa)
{
if(yes[x]==1)cnt[x]++;
for(auto i:es[x])
{
if(i==pa)continue;
dfs1(i,x);
cnt[x]+=cnt[i];
}
}
tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>s;
int ans;
int ans0;
map<ll,ll>mp;
void dfs2(int x,int pa)
{
if(yes[x]==2)
{
mp[suf[x]-val[x]-val[x]]++;
s.insert(((suf[x]-val[x]-val[x])<<8)+mp[suf[x]-val[x]-val[x]]);
}
if(!s.empty())
{
for(auto i:es[x])
{
if(i==pa)continue;
ll tmp=suf[i];
auto it=s.upper_bound(((tmp+1)<<8)-1);
// cout<<((tmp<<9)-1)<<endl;
if(it==s.begin())
{
dfs2(i,x);
}
else if(it!=s.end())
{
int ttmp=s.order_of_key(*it);
ans=max(ans,ttmp+ans0-cnt[i]);
dfs2(i,x);
}
else
{
ans=max(ans,ans0-cnt[i]+(int)s.size());
dfs2(i,x);
}
}
}
else
{
for(auto i:es[x])
{
if(i==pa)continue;
dfs2(i,x);
}
}
if(yes[x]==2)
{
auto it=s.lower_bound((suf[x]-val[x]-val[x])<<8);
s.erase(it);
}
}
int main()
{
int n;
IOS;
cin>>n;
int i;
for(i=1;i<=n;i++)cin>>val[i];
if(n==1)
{
cout<<0;
return 0;
}
for(i=1;i<=n;i++)
{
cin>>x[i];
y[i]=i;
if(i==1)continue;
es[x[i]].push_back(i);
es[i].push_back(x[i]);
}
// int ans=0;
dfs(1,0);
for(i=1;i<=n;i++)
{
if(pre[i]-val[i]>=val[i]&&suf[i]-val[i]<=val[i])
{
yes[i]=1;
ans++;
}
}
dfs1(1,0);
for(i=1;i<=n;i++)
{
if(!yes[i])
{
if(pre[i]-val[i]>=val[i])
{
yes[i]=2;
}
}
}
ans0=ans;
dfs2(1,0);
cout<<ans;
return 0;
}
``````

3 收藏 评论