题解 | #最少胜利题数#
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;
}
