8000 Create 1949.cpp · dkim-coder/basic-algo-lecture@a190c85 · GitHub
[go: up one dir, main page]

Skip to content

Commit a190c85

Browse files
Create 1949.cpp
1 parent 2303e9e commit a190c85

File tree

1 file changed

+40
-0
lines changed

1 file changed

+40
-0
lines changed

Appendix E/1949.cpp

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -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

Comments
 (0)
0