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\n",res);
60     for(int i = 1 ; i <= n ; i++){
61         if(!id[i])    dfs2(i);
62     }//从没父亲的节点开始搜叭 
63     printf("\n");
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 << '\n';
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 << '\n';
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 }