给你一个序列aa

定义aa的一个排列pp合法需要满足∀j≤k\forall j\le k，不存在apj=pka_{p_j}=p_k

定义一个排列的权值是

求最大权值

1≤n≤500000,0≤ai≤n,1≤wi≤109,∑wi≤1.5×10131\le n \le 500000,0 \le a_i \le n,1 \le w_i \le 10^9 ,\sum w_i \le 1.5\times10^{13}

Luogu P4437

Solution

首先可以发现，若 ，则 一定要排在 之前

所以把所有 连边，最后的图如果有环则无解，否则就是一颗树

那么题目转化为一棵树，按照某种顺序 依次选取所有点, 满足每个点的父亲比自己先选, 在此基础上最大化 .

考虑直接贪心，对于当前剩余权值最小的点，选了它的父亲后一定马上就会选它，然后就把它和它父亲缩成一个连通块

那么当前剩下的所有连通块中，应该先选哪个呢？

考虑两个连通块设i,ji,j，那么ii比jj优则需要满足

wi∗leni+wj∗(leni+lenj)>wj∗sj+wi∗(leni+lenj)w_i*len_i+w_j*(len_i+len_j) > w_j * s_j + w_i * (len_i + len_j)（ww表示该连通块中所有点权值和，lenlen表示点数）

即wileni<wjlenj\frac{w_i}{len_i} < \frac{w_j}{len_j}

因此按照wileni\frac{w_i}{len_i}从小到大选，用可删除堆+并查集维护即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

inline void proc_status()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 5e5 + 100;

int N, A[Maxn], W[Maxn];
int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];
int Vis[Maxn], cnt;

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

inline void dfs (int x)
{
	if (Vis[x]) { puts("-1"); exit(0); }
	++cnt;
	Vis[x] = 1;
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		dfs(y);
	}
}

struct node
{
	LL w, len;
	int id;
	inline int operator < (const node &a) const
	{
		if (a.w * len == w * a.len) return a.id < id;
		return a.w * len < w * a.len;
	}
	inline int operator == (const node &a) const
	{
		return ((a.w == w) && (a.len == len) && (a.id == id));
	}
};

struct Heap
{
	priority_queue <node> a, b;

	inline void del () { while (!b.empty() && a.top() == b.top()) a.pop(), b.pop(); }

	inline void pop () { del(); a.pop(); }

	inline void erase (node k) { b.push(k); }

	inline node top () { del(); return a.top(); }

	inline int empty () { del(); return a.empty(); }

	inline void push (node k) { a.push(k); }
}Q;

LL ans;

namespace DSU
{
	int fa[Maxn];
	LL w[Maxn], len[Maxn];
	inline void init () { for (int i = 1; i <= N; ++i) fa[i] = i, w[i] = W[i], len[i] = 1, Q.push((node){w[i], len[i], i}); }

	inline int find (int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

	inline void link (int x, int y)
	{
		if (y) Q.erase((node){w[y], len[y], y});
		ans += w[x] * len[y];
		w[y] += w[x], len[y] += len[x], fa[x] = y;
/**/	w[x] = len[x] = 0;
		if (y) Q.push((node){w[y], len[y], y});
	}
}

inline void Solve ()
{
	dfs(0);
	if (cnt <= N) { puts("-1"); return ; }

	DSU :: init();
/**/while (!Q.empty())
	{
		int x = Q.top().id, y = DSU :: find(A[x]); Q.pop();
		DSU :: link (x, y);
	}
	cout<<ans<<endl;
}

inline void Input ()
{
	N = read();
	for (int i = 1; i <= N; ++i) A[i] = read(), add_edge (A[i], i);
	for (int i = 1; i <= N; ++i) ans += (W[i] = read());
}

int main()
{
#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	Input();
	Solve();
	return 0;
}