脚本宝典收集整理的这篇文章主要介绍了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 << ' ';
}

脚本宝典总结

以上是脚本宝典为你收集整理的cf1388 D. Captain Flint and Treasure全部内容，希望文章能够帮你解决cf1388 D. Captain Flint and Treasure所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。