1 条题解
-
0
hqy
```````````````````````````````````````````````````````````````````````````````
MOD
@ 2026-11-8 22:08:28精华 这道题是一个树上DP,详解看注释
#include<iostream> #include<vector> using namespace std; const int N = 6*1e3+10; // 题目最大值 int n,a[N],dp[N][2]; // dp[i][0/1] 表示第i好节点选/不选 vector<int> e[N]; bool fa[N]; // 用来找根节点,表示第x个节点有没有父节点 void dfs(int x) { // 树上dp dp[x][0] = a[x]; // 如果选,那就自身有这只笔的价值 dp[x][1] = 0; // 如果不选,那就没有价值 for(int i = 0;i<e[x].size();i++) { // 枚举子节点 int y = e[x][i]; // 子节点 dfs(y); // 寻找子节点 dp[x][0]+=dp[y][1]; // 如果选了,那下面的子节点就一定不能选 dp[x][1]+=max(dp[y][0],dp[y][1]); // 因为这个节点没选,所以下面的子节点可以选或不选 } } int main() { cin>>n; for(int i = 1;i<=n;i++) { cin>>a[i]; } for(int i = 1;i<n;i++) { int x,y; cin>>x>>y; e[y].push_back(x); // 这里用有向边,就可以不用判定父节点 fa[x] = true; // x有了父节点 } int root = 1; // 寻找根节点 while(fa[root]) { // 便利每个节点 root++; } dfs(root); // dp开始 cout<<max(dp[root][0],dp[root][1]); // 根节点选/不选的最大值 return 0; }
- 1
信息
- ID
- 10
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 显示难度普及
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者