8000
We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
There was an error while loading. Please reload this page.
1 parent 2303e9e commit a190c85Copy full SHA for a190c85
Appendix E/1949.cpp
@@ -0,0 +1,40 @@
1
+#include <bits/stdc++.h>
2
+using namespace std;
3
+
4
+int n;
5
+int a[10005];
6
+int d1[10005];
7
+int d2[10005];
8
9
+vector<int> adj[10005];
10
11
+// d1[cur]와 d2[cur]를 계산하는 함수
12
+void dfs(int cur, int par){
13
+ d1[cur] = a[cur];
14
+ d2[cur] = 0;
15
+ for(int nxt : adj[cur]){
16
+ if(par == nxt) continue;
17
+ dfs(nxt, cur);
18
+ d1[cur] += d2[nxt];
19
+ d2[cur] += max(d1[nxt], d2[nxt]);
20
+ }
21
+}
22
23
+int main(){
24
+ ios::sync_with_stdio(0);
25
+ cin.tie(0);
26
27
+ cin >> n;
28
+ for(int i = 1; i <= n; i++)
29
+ cin >> a[i];
30
31
+ for(int i = 0; i < n-1; i++){
32
+ int u, v;
33
+ cin >> u >> v;
34
+ adj[u].push_back(v);
35
+ adj[v].push_back(u);
36
37
38
+ dfs(1, 0);
39
+ cout << max(d1[1], d2[1]);
40
0 commit comments