HNOI2018 排列
给定\(a_1,a_2\dots a_n,w_1,w_2\dots w_n\)，定义一个\(1\dots n\)排列（设\(i\)的位置为\(p_i\)，且\(p_0=0\)）是合法的当且仅当\(\forall_i p_{a_i}<p_i\)。
定义一个排列的权值为\(\sum w_ip_i\)，求合法排列中权值的最大值。
题解
模型转化
对于\(p_{a_i}<p_i\)的限制，连一条\(a_i,i\)的边。
如果出现了环则无解，否则一定是形成了一个以0为根n+1点的树。
然后就是poj2054原题了。
做法
由于我们希望最后权值尽量大，所以就希望\(w_i\)小的靠前选择。
当你选出\(w_i\)最小的i，i一定尽量在父亲之后选择。
这样就形成了一个"联通块"
考虑两个联通块的优先顺序：
设两个联通块的权值和和点数分别是\(w_1,s_1,w_2,s_2\)，那么1在2前面需要\(s_1w_2\ge w_1s_2\)，也就是\(\frac{w_1}{s_1}\le \frac{w_2}{s_2}\)
所以对于一个联通块，直接按平均权值当做一个点就可以了。
以及每次选出一个联通块A时（A的父亲的联通块是F），对答案的贡献就是\(w_As_F\)(在F所在联通块全部选完再选A的联通块)。
这就完了。
/*
Author: CNYALI_LK
LANG: C++
PROG: 4437.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
#define mp3(a,b,c) make_pair((long double)(a)/b,c)
using namespace std;
typedef long long ll;
typedef pair<long double,ll> pii;
typedef pair<pii,ll> piii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
ll fa[500005],w[500005],bel[500005],siz[500005];
ll belong(ll x){return x==bel[x]?x:bel[x]=belong(bel[x]);}
__gnu_pbds::priority_queue<pii,greater<pii> >p;
__gnu_pbds::priority_queue<pii,greater<pii> >::point_iterator it[500005];
int main(){
#ifdef cnyali_lk
freopen("4437.in","r",stdin);
freopen("4437.out","w",stdout);
#endif
ll n;
read(n);
for(ll i=1;i<=n;++i)bel[i]=i;
for(ll i=1;i<=n;++i){read(fa[i]);if(belong(i)==belong(fa[i])){write("-1\n");return 0;}bel[belong(i)]=belong(fa[i]);}
for(ll i=1;i<=n;++i)bel[i]=i;
bel[0]=0;
it[0]=p.push(mp3(1e18,1,0LL));
for(ll i=1;i<=n;++i){
read(w[i]);
it[i]=p.push(mp3(w[i],1,i));
siz[i]=1;
}
w[0]=1e18;
siz[0]=1;
ll ans=0;
for(;n;--n){
pii a=p.top();
p.pop();
ll f=belong(fa[a.y]);
ans+=w[a.y]*siz[f];
siz[f]+=siz[a.y];
w[f]+=w[a.y];
bel[a.y]=f;
p.modify(it[f],mp3(w[f],siz[f],f));
}
printf("%lld\n",ans);
return 0;
}