首页 > 代码库 > 蓝桥杯 结点选择
蓝桥杯 结点选择
思路:
无根树转有根树 + 树形dp。
实现:
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int MAXN = 100000; 9 const int INF = 0x3f3f3f3f; 10 11 int n, x, y; 12 int dp[MAXN + 5][2], a[MAXN + 5], f[MAXN + 5], vis[MAXN + 5]; 13 vector<int> G[MAXN + 5]; 14 15 void trans(int root, int p) 16 { 17 for (int i = 0; i < G[root].size(); i++) 18 { 19 int tmp = G[root][i]; 20 if (tmp != p) 21 trans(tmp, f[tmp] = root); 22 } 23 } 24 25 void build() 26 { 27 for (int i = 1; i <= n; i++) 28 G[i].clear(); 29 for (int i = 2; i <= n; i++) 30 { 31 G[f[i]].push_back(i); 32 } 33 } 34 35 void dfs(int now) 36 { 37 vis[now] = 1; 38 for (int i = 0; i < G[now].size(); i++) 39 { 40 int tmp = G[now][i]; 41 if (!vis[tmp]) 42 { 43 dfs(tmp); 44 } 45 dp[now][1] += dp[tmp][0]; 46 dp[now][0] += max(dp[tmp][1], dp[tmp][0]); 47 } 48 dp[now][1] += a[now]; 49 } 50 51 int main() 52 { 53 cin >> n; 54 for (int i = 1; i <= n; i++) 55 { 56 scanf("%d", &a[i]); 57 } 58 for (int i = 0; i < n - 1; i++) 59 { 60 scanf("%d %d", &x, &y); 61 G[x].push_back(y); 62 G[y].push_back(x); 63 } 64 int ans = -INF; 65 trans(1, -1); 66 build(); 67 memset(dp, 0, sizeof(dp)); 68 memset(vis, 0, sizeof(vis)); 69 dfs(1); 70 ans = max(ans, max(dp[1][0], dp[1][1])); 71 printf("%d\n", ans); 72 return 0; 73 }
蓝桥杯 结点选择
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。