Problem
Description
给定 \(n\) 个整数 \(a_1, a_2, \ldots , a_n(0 \le a_i \le n)\),以及 \(n\) 个整数 \(w_1, w_2, …, w_n\)。称 \(a_1, a_2, \ldots , a_n\) 的一个排列 \(a_{p[1]}, a_{p[2]}, \ldots , a_{p[n]}\) 为 \(a_1, a_2, \ldots , a_n\) 的一个合法排列,当且仅当该排列满足:对于任意的 \(k\) 和任意的 \(j\),如果 \(j \le k\),那么 \(a_{p[j]}\) 不等于 \(p[k]\)。(换句话说就是:对于任意的 \(k\) 和任意的 \(j\),如果 \(p[k]\) 等于 \(a_{p[j]}\),那么 \(k<j\)。)
定义这个合法排列的权值为 \(w_{p[1]} + 2w_{p[2]} + \ldots + nw_{p[n]}\)。你需要求出在所有合法排列中的最大权值。如果不存在合法排列,输出 \(-1\)。
样例解释中给出了合法排列和非法排列的实例。
Input Format
第一行一个整数 \(n\)。
接下来一行 \(n\) 个整数,表示 \(a_1,a_2,\ldots , a_n\)。
接下来一行 \(n\) 个整数,表示 \(w_1,w_2,\ldots ,w_n\)。
Output Format
输出一个整数表示答案。
Sample
Input 1
3
0 1 1
5 7 3
Output 1
32
Input 2
3
2 3 1
1 2 3
Output 2
-1
Input 3
10
6 6 10 1 7 0 0 1 7 7
16 3 10 20 5 14 17 17 16 13
Output 3
809
Explanation
Explanation for Input 1
对于 \(a_1=0,a_2=1,a_3=1\),其排列有
- \(a_1=0,a_2=1,a_3=1\),是合法排列,排列的权值是 \(1*5+2*7+3*3=28\);
- \(a_2=1,a_1=0,a_3=1\),是非法排列,因为 \(a_{p[1]}\) 等于 \(p[2]\);
- \(a_1=0,a_3=1,a_2=1\),是合法排列,排列的权值是 \(1*5+2*3+3*7=32\);
- \(a_3=1,a_1=0,a_2=1\),是非法排列,因为 \(a_{p[1]}\) 等于 \(p[2]\);
- \(a_2=1,a_3=1,a_1=0\),是非法排列,因为 \(a_{p[1]}\) 等于 \(p[3]\);
- \(a_3=1,a_2=1,a_1=0\),是非法排列,因为 \(a_{p[1]}\) 等于 \(p[3]\)。
因此该题输出最大权值 \(32\)。
Explanation for Input 2
对于 \(a_1=2,a_2=3,a_3=1\),其排列有:
- \(a_1=2,a_2=3,a_3=1\),是非法排列,因为 \(a_{p[1]}\) 等于 \(p[2]\);
- \(a_2=3,a_1=2,a_3=1\),是非法排列,因为 \(a_{p[1]}\) 等于 \(p[3]\);
- \(a_1=2,a_3=1,a_2=3\),是非法排列,因为 \(a_{p[1]}\) 等于 \(p[3]\);
- \(a_3=1,a_1=2,a_2=3\),是非法排列,因为 \(a_{p[2]}\) 等于 \(p[3]\);
- \(a_2=3,a_3=1,a_1=2\),是非法排列,因为 \(a_{p[2]}\) 等于 \(p[3]\);
- \(a_3=1,a_2=3,a_1=2\),是非法排列,因为 \(a_{p[1]}\) 等于 \(p[3]\)。
因此该题没有合法排列。
Range
对于前 \(20\%\) 的数据,\(1 \le n \le 10\);
对于前 \(40\%\) 的数据,\(1 \le n \le 15\);
对于前 \(60\%\) 的数据,\(1 \le n \le 1000\);
对于前 \(80\%\) 的数据,\(1 \le n \le 100000\);
对于 \(100\%\) 的数据,\(1 \le n \le 500000\),\(0 \le a_i \le n (1 \le i \le n)\),\(1 \le w_i \le 10^9\) ,所有 \(w_i\) 的和不超过 \(1.5 \times 10^{13}\)。
Algorithm
并查集
Mentality
这一题的题面很神仙,略难懂。
简而言之,有一棵树,告诉你每个节点的父亲和权值,只有选择了父亲才能选择儿子,如果当前选到的节点是你选的第 \(i\) 个,那么它的贡献为 \(i×\)权值 。问最大的总贡献。必须选完整棵树。
那么数据里不能有环,否则输出 \(-1\) 。
除去无解的情况,我们可以开始想想怎么做了:
首先想到一个很显然的错误贪心,那就是用一个优先队列维护当前能选的所有点,优先选权值最小的,不过这很好卡,若 \(i\) 的权值为 \(1e9\) ,其他所有节点的权值为 \(1e9-1\) ,\(i\) 的子树权值都为 \(1\) 。那这个贪心就死掉了。
但是不打紧,我们可以考虑这样一些东西:对于一个节点 \(i\) ,如果它的权值是最小的,那么当我们选完了 \(fa[i]\) ,我们必定会选择 \(i\) ,也就是说,对于权值最小的 \(i\) ,它一定会在 \(fa[i]\) 之后挨着选择。
所以我们可以考虑将最后答案的选择序列分割为 \(n\) 块,利用这个贪心一块块按顺序合并。
但是,对于两块 \(size>1\) 的序列,我们如何合并它们呢?
假设我已经选到了第 \(i\) 位,之后要按顺序合并 \(a\) 与 \(b\) 两块序列。
设 \(W_i\) 为序列 \(i\) 内元素权值和,\(w_{i_j}\) 代表序列 \(i\) 内第 \(j\) 个元素的权值。
那么如果我们先选 \(a\) 再选 \(b\) ,贡献就会是这样的:
\[ \sum_{j=1}^{size_a}(i+j)\cdot w_{a_j}+\sum_{j=1}^{size_b}(i+size_a+j)\cdot w_{b_j} \]
而先选 \(b\) 的话,贡献如下:
\[ \sum_{j=1}^{size_b}(i+j)\cdot w_{b_j}+\sum_{j=1}^{size_a}(i+size_b+j)\cdot w_{a_j} \]
则先选 \(a\) 更优,当且仅当 \(size_a*sum_b>size_b*sum_a\) 。
那么贪心策略便彻底确定下来了,我们只需要按证明出的结论的优劣性贪心选择并合并即可。
过程如下:
- 初始化并查集
- 选择堆顶元素,并检查元素是否为所在集合的根
- 合并当前元素与父亲所在集合,并计算对答案的贡献
完毕。
Code
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,cnt,Fa[500001],head[500001],nx[500001],to[500001];
int fa[500001],size[500001];
long long w[500001],ans;
bool vis[500001],flag;
struct node
{
int x,size;
long long w;
bool operator<(const node b)const{return w*b.size>b.w*size;}//定义比较函数
};
priority_queue <node> q;
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void Push(int x)
{
q.push(node{x,size[x],w[x]});
}
void Merge(int f,int x)
{
ans+=1ll*size[f]*w[x];//计算贡献
w[f]+=w[x];
size[f]+=size[x];
}//合并集合
void dfs(int x)
{
if(flag)return;
if(vis[x])flag=1;
vis[x]=1,cnt++;
for(int i=head[x];i;i=nx[i])
dfs(to[i]);
}
int main()
{
freopen("4437.in","r",stdin);
freopen("4437.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&Fa[i]);
nx[i]=head[Fa[i]],to[i]=i;
head[Fa[i]]=i;
}
dfs(0);
if(cnt<n||flag)
{
cout<<"-1";
return 0;
}//判断不合法情况--环
for(int i=1;i<=n;i++)
{
scanf("%lld",&w[i]);
ans+=w[i];
fa[i]=i,size[i]=1;
Push(i);
}//初始化并查集与答案
int x,f;
while(!q.empty())
{
x=q.top().x;
q.pop();
if(x!=find(x))continue;//判断是否为并查集根部元素
x=find(x);
fa[x]=f=find(Fa[x]);//合并
Merge(f,x);
if(f)Push(f);//加入堆内
}
cout<<ans;
}