cf1388 D. Captain Flint and Treasure

题意：

给定数组 \(a[],b[]\)，初始答案为0。每次选一个 \(i\)，使答案加上 \(a_i\)，\(a[b_i]\) 也加上 \(a_i\) 。注意 \(a[b_i]\) 加上 \(a_i\) 就行了，不会连锁反应。

要求每个 \(i\) 选一次，最大化答案并输出方案。

思路：

对于每个点，我们希望在选它之前，先选完它的所有正的前驱点。如果选完它的正的前驱点之后它还是负的，就放最后选，不要拖累后面

其实是一个森林，但每棵树都是颠倒的。一开始写了一堆拓扑排序、栈之类差点去世。实际上只需建反图，然后弄个超级源点，就变成一棵树了

对所有正（不管是初始就为正还是最后为正）的点，我们希望它影响后面的点，所以顺序输出；对所以没法变正的点，尽量不影响后面的，所以倒序输出

const signed N = 2e5 + 3; ll n, a[N], ans; vector<int> G[N];  vector<int> ve[2]; //正的,负的 void dfs(int u) {     for(int v : G[u])         dfs(v), a[u] += max(0ll, a[v]); //负儿子别影响爹     if(u) ans += a[u], ve[a[u]>0].pb(u); }  signed main() {     iofast;     cin >> n;     for(int i = 1; i <= n; i++) cin >> a[i];     for(int i = 1, u; i <= n; i++)         cin >> u, G[max(0,u)].pb(i);      dfs(0);      cout << ans << endl;     for(int i : ve[1]) cout << i << ' ';     reverse(all(ve[0])); //负的倒序     for(int i : ve[0]) cout << i << ' '; }