这个条件给的有点诡异:对于任意的 \(a_{p_j}=p_k\),都有 \(k<j\)。
那么对于某个 \(a_x=y\),意思就是 \(y\) 在 \(p\) 中的位置小于 \(x\) 在 \(p\) 中的位置。
那么如果我们连边 \((a_x,x)\),就是要求图中没有环,是一棵树,而且父亲在 \(p\) 中的位置要小于儿子在 \(p\) 中的位置。
再看一下要求:按 \(p\) 的顺序把 \(i\times w_{p_i}\) 加起来得到总权值,找到一种 \(p\) 的顺序使得总权值最大。
是个树上全序问题(可参考 AGC023F),现在有若干个连通块,我们要给这些连通块一种顺序使得总权值最大。
仍然考虑最优顺序下,相邻的两个连通块 \(a\) 和 \(b\),它们的大小分别为 \(sz_a,sz_b\),它们各自的 \(w\) 的和分别为 \(W_a,W_b\),它们各自的总权值分别为 \(V_a,V_b\)。设 \(a\) 之前的总权值为 \(V\),\(a\) 之前的点的总数为 \(S\)。
交换前:\(ans_1=V+S\cdot W_a+V_a+(S+sz_a)\cdot W_b+V_b\)。
交换后:\(ans_2=V+S\cdot W_{b}+V_b+(S+sz_b)\cdot W_a+V_a\)。
强制令 \(ans_1\geq ans_2\),得到 \(\dfrac{W_a}{sz_a}\leq \dfrac{W_b}{sz_b}\),于是我们直接按 \(\dfrac{W_a}{sz_a}\) 从小到大排序即可。
#include<bits/stdc++.h>
#define N 500010
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int n,fa[N],rt[N];
int sz[N];
ll w[N],v[N];
bool vis[N];
bool del[N];
vector<int>e[N];
void dfs(int u)
{
if(vis[u])
{
puts("-1");
exit(0);
}
vis[u]=1;
for(int v:e[u]) dfs(v);
}
int find(int x)
{
return x==rt[x]?x:(rt[x]=find(rt[x]));
}
struct cmp
{
inline bool operator()(int a,int b) const//这里加inline会大大地优化时间,不然过不去
{
if(w[a]*sz[b]==w[b]*sz[a]) return a<b;
return w[a]*sz[b]<w[b]*sz[a];
}
};
set<int,cmp>s;
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
rt[i]=i;
fa[i]=read();
if(fa[i]) e[fa[i]].push_back(i);
}
for(int i=1;i<=n;i++)
if(!fa[i]) dfs(i);
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
puts("-1");
return 0;
}
}
for(int i=1;i<=n;i++)
v[i]=w[i]=read(),sz[i]=1;
for(int i=1;i<=n;i++)
s.insert(i);
del[0]=1;
ll V=0,S=0;
while(!s.empty())
{
int u=(*s.begin());
s.erase(s.begin());
int f=find(fa[u]);
if(del[f])
{
del[u]=1;
V+=S*w[u]+v[u];
S+=sz[u];
continue;
}
s.erase(f);
rt[u]=f;
v[f]+=sz[f]*w[u]+v[u];
w[f]+=w[u];
sz[f]+=sz[u];
s.insert(f);
}
printf("%lld\n",V);
return 0;
}
标签:sz,ch,AHOI2018,int,总权值,HNOI,cdot,全序,ans
From: https://www.cnblogs.com/ez-lcw/p/16837425.html