链接
https://codeforces.com/contest/1388/problem/D
题意
数组 $a,b$ 长度为 $n$，选择一个 $i$，进行如下操作
- $ans+=a_i$
- $a_{b_i}+=a_i(b_i\ne-1)$
求一个 $1\sim n$ 的排列使按此排列操作得到的 $ans$ 最大
思路
$i$ 对 $b_i$ 有贡献，即 $i$ 可以到达 $b_i$，反向建图，我们可以得到若干个树形图，树根为 $b_i=-1$ 的点
对于某个节点 $u$ 的儿子 $v$，若 $a_v>0$，贡献为正，则先对 $v$ 进行操作，否则 $v$ 只能在 $u$ 操作后再操作，可以把 $v$ 存进数组 $t$
遍历完所有点后，倒序操作数组 $t$ 中的所有点，因为后加入的点可能为先加入点的祖先
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,b[N],res[N],cnt;
long long a[N],tot;
vector<int> G[N],t;
void dfs(int u,int fa) {
for(auto v:G[u]) dfs(v,u);
if(a[u]>0) res[++cnt]=u,tot+=a[u],a[fa]+=a[u];
else t.push_back(u);
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) {
if(b[i]==-1) continue;
G[b[i]].push_back(i);
}
for(int i=1;i<=n;i++) if(b[i]==-1) dfs(i,0);
for(int i=t.size()-1;i>=0;i--) res[++cnt]=t[i],tot+=a[t[i]];
printf("%lld\n",tot);
for(int i=1;i<=n;i++) printf("%d ",res[i]);
puts("");
return 0;
}
|