dfs一次解决sum
第二次解决已处理的点的顺序以及未处理的点的顺序
已处理，则存入队列，靠近叶子的点先出
未处理，则存入栈，靠近顶端的点先出
一共跑了三次树
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<cmath>
5 #include<vector>
6 #define ll long long
7 using namespace std;
8 const int N = 2e5 + 10;
9 int n;
10 ll a[N], sum[N];
11 int id[N];
12
13 vector<int> v[N];
14 ll res = 0;
15
16 void dfs(int now)
17 {
18 sum[now] = a[now];
19 for(int i = 0 ; i < v[now].size() ; i++){
20 int son = v[now][i];
21 dfs(son);
22 if(sum[son] > 0) sum[now] += sum[son];
23 }
24 }
25
26 void dfs2(int now)
27 {
28 for(int i = 0 ; i < v[now].size() ; i++){
29 int son = v[now][i];
30 if(sum[son] >= 0) dfs2(son);
31 }
32 printf("%d ",now);
33 for(int i = 0 ; i < v[now].size() ; i++){
34 int son = v[now][i];
35 if(sum[son] < 0) dfs2(son);
36 }
37 }
38
39 int main(){
40 scanf("%d",&n);
41 for(int i = 1 ; i <= n ; i++){
42 scanf("%lld",&a[i]);
43 }
44 for(int i = 1 ; i <= n ; i++){
45 int x;scanf("%d",&x);
46 if(x != -1){
47 v[x].push_back(i);
48 id[i]++;
49 }
50 }
51
52 for(int i = 1 ; i <= n ; i++){
53 if(!id[i]) dfs(i);
54 }
55 for(int i = 1 ; i <= n ; i++){
56 res += sum[i];
57 }
58
59 printf("%lld
",res);
60 for(int i = 1 ; i <= n ; i++){
61 if(!id[i]) dfs2(i);
62 }//从没父亲的节点开始搜叭
63 printf("
");
64 return 0;
65 }
一次dfs解决
每访问一个节点，直接加到res，每个节点至少加一次
若当前节点为正，直接加到它的父亲上（有父亲），同时加到队列里面
若当前节点为负，直接加到栈里面（reverse的vector）
1 #include <bits/stdc++.h>
2 #define ll long long
3 #define all(a) a.begin(),a.end()
4
5 using namespace std;
6
7 vector <vector <int> > edge;
8 vector <ll> a;
9 vector <int> b, used;
10 vector <int> order[2];
11 ll ans;
12 inline void dfs (int v) {
13 used[v] = 1;
14 for (int to : edge[v]) {
15 if (!used[to]) dfs(to);
16 }
17 ans += a[v];
18 if (b[v] != -1 && a[v] > 0) {
19 a[b[v]] += a[v];
20 }
21 if (a[v] > 0) {
22 order[0].push_back(v);
23 }
24 else {
25 order[1].push_back(v);
26 }
27 }
28 inline void solve () {
29 for (auto &i : edge) i.clear();
30 edge.clear();
31 a.clear();
32 order[0].clear();
33 order[1].clear();
34 b.clear();
35 used.clear();
36 int n, x;
37 cin >> n;
38 edge.resize(n);
39 a.resize(n);
40 b.resize(n);
41 for (auto &i : a) cin >> i;
42 for (int i = 0; i < n; i++) {
43 cin >> x;
44 if (x != -1) {
45 --x;
46 edge[x].push_back(i);
47 }
48 b[i] = x;
49 }
50 ans = 0;
51 used.assign(n, 0);
52 for (int i = 0; i < n; i++) {
53 if (!used[i]) {
54 dfs(i);
55 }
56 }
57 cout << ans << '
';
58 reverse(all(order[1]));
59 for (auto &i : order[0]) cout << i + 1 << ' ';
60 for (auto &i : order[1]) cout << i + 1 << ' ';
61 cout << '
';
62 }
63 main()
64 {
65 ios::sync_with_stdio(0);
66 ios_base::sync_with_stdio(0);
67 cin.tie(0);
68 cout.tie(0);
69 solve();
70 }