E

基于 库的通俗易懂的题解

通过题意我们不难发现，如果删除某条边，那么对剩下的某节点来说，其祖先节点的权值和一定是不变的，受影响的仅有其子树节点的权值和。因此，如果删除一条边后，有节点满足了成为关键节点的条件，那么它一定满足条件 而不满足条件 。

我们可以预处理出每个节点的树上前缀和 和后缀和 ,并用一个数组 记录是否满足条件 ,如果 是 ,那么说明这个点未删边时就满足了两个条件，是 则说明只满足条件 ,再用一个数组 记录已经是关键节点的数量的树上后缀和。

之后，我们考虑通过 来枚举删除哪条边。不难发现，如果删除了一条边 ,相当于给其所有祖先数组的 减了 。此时，对某个祖先节点 来说，只要满足 就说明这个节点可以成为关键节点。

现在问题转化为如何在最多 的时间复杂度内求出 的节点的个数。如果使用 或 ,那么我们无法知道到底有多少个数是满足条件的，也就是说我们无法知道它是范围内第几大 ，因此，选择用 库的平衡树来维护这些数据，其自带的 函数可以完美满足我们的要求。

然而 不支持插入相同数据，我们可以用一个 记录相同数据的出现次数，将数据左移 位后加上出现的次数就可以了。通过 函数查找大于 的最小位置，用 函数求得此时树内 的值的个数，记为 ,那么删掉这条边后的答案就是 。其中 是一条边都未删时的答案。遍历后取 即可。

// Problem: 最大稳定数值
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/84528/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#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;
}