十五月明

用户名：dotcpp0605328

访问量：5432

签　名：

等　　级
排　　名	319
经　　验	5465
参赛次数	0
文章发表	87
年　　龄	18
在职情况	学生
学　　校	曲阜师范大学
专　　业	人工智能

　　自我简介：

Easy

TA的其他文章

线段（贪心）
浏览：5

加工生产调度
浏览：2

发工资咯记way
浏览：4

你可能喜欢

蓝桥杯2015年第六届真题-生命之树树形dp

　　作者: 十五月明　　　　发表时间：2024-11-04 17:10:05 浏览：8　|　评论：0　

原题链接：蓝桥杯2015年第六届真题-生命之树

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=100010,M=2*N;
    int n;
    int w[N];
    int h[N],e[M],ne[M],idx;
    ll f[N];
    
    void add(int a,int b){
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    }
    void dfs(int u,int father){
        f[u]=w[u];
        for(int i=h[u];~i;i=ne[i]){
            int j=e[i];
            if(j==father) continue;
            dfs(j,u);
            f[u]+=max(f[j],0ll);
        }
    }
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>w[i];
        memset(h,-1,sizeof h);
        for(int i=1;i<n;i++){
            int a,b; cin>>a>>b;
            add(a,b),add(b,a);
        }
        dfs(1,-1);
        ll res=f[1];
        for(int i=2;i<=n;i++) res=max(res,f[i]);
        cout<<res<<endl;
        return 0;
    }

### 头文件和命名空间

```cpp
#include<bits/stdc++.h>
using namespace std;
```
- `#include<bits/stdc++.h>`：这是一个非标准的头文件，包含了C++标准库中的几乎所有头文件。在竞赛编程中，为了简化代码，经常使用这个头文件。
- `using namespace std;`：这行代码允许我们直接使用标准库中的名称，而不需要`std::`前缀。

### 类型定义和常量

```cpp
typedef long long ll;
const int N=100010,M=2*N;
```
- `typedef long long ll;`：定义了一个别名`ll`，代表`long long`类型，用于存储大整数。
- `const int N=100010,M=2*N;`：定义了两个常量`N`和`M`，分别表示节点的最大数量和边的最大数量。

### 变量定义

```cpp
int n;
int w[N];
int h[N],e[M],ne[M],idx;
ll f[N];
```
- `int n;`：定义了一个变量`n`，用于存储图中节点的数量。
- `int w[N];`：定义了一个数组`w`，用于存储每个节点的权重。
- `int h[N],e[M],ne[M],idx;`：定义了三个数组`h`、`e`和`ne`，以及一个索引变量`idx`。这些用于构建图的邻接表。
- `ll f[N];`：定义了一个数组`f`，用于存储每个节点的最大路径和。

### 图的构建

```cpp
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
```
- `void add(int a,int b){...}`：定义了一个函数`add`，用于在图中添加一条从节点`a`到节点`b`的边。
  - `e[idx]=b`：将边的终点`b`存储在数组`e`中。
  - `ne[idx]=h[a]`：将边的前一条边的索引存储在`ne`中，实现链表的后继。
  - `h[a]=idx++`：将当前边的索引存储为节点`a`的头边索引，并递增`idx`。

### 深度优先搜索（DFS）

```cpp
void dfs(int u,int father){
    f[u]=w[u];
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father) continue;
        dfs(j,u);
        f[u]+=max(f[j],0ll);
    }
}
```
- `void dfs(int u,int father){...}`：定义了一个深度优先搜索函数`dfs`，用于计算每个节点的最大路径和。
  - `f[u]=w[u];`：初始化节点`u`的最大路径和为其权重。
  - `for(int i=h[u];~i;i=ne[i]){...}`：遍历节点`u`的所有邻接边。
    - `int j=e[i];`：获取边的终点`j`。
    - `if(j==father) continue;`：如果`j`是父节点，则跳过，避免重复计算。
    - `dfs(j,u);`：递归地计算子节点`j`的最大路径和。
    - `f[u]+=max(f[j],0ll);`：更新节点`u`的最大路径和，加上子节点`j`的最大路径和（如果为正数）。

### 主函数

```cpp
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs(1,-1);
    ll res=f[1];
    for(int i=2;i<=n;i++) res=max(res,f[i]);
    cout<<res<<endl;
    return 0;
}
```
- `int main(){...}`：定义了主函数，程序的入口点。
  - `cin>>n;`：读取节点数量`n`。
  - `for(int i=1;i<=n;i++) cin>>w[i];`：读取每个节点的权重并存储在数组`w`中。
  - `memset(h,-1,sizeof h);`：使用`memset`函数将数组`h`初始化为-1，表示没有边。
  - `for(int i=1;i<n;i++){...}`：读取每条边的信息，并使用`add`函数添加到图中。
    - `int a,b; cin>>a>>b;`：读取边的起点`a`和终点`b`。
    - `add(a,b),add(b,a);`：添加边`a`到`b`和`b`到`a`，构建无向图。
  - `dfs(1,-1);`：从节点1开始调用`dfs`函数，计算每个节点的最大路径和。
  - `ll res=f[1];`：初始化结果`res`为节点1的最大路径和。
  - `for(int i=2;i<=n;i++) res=max(res,f[i]);`：遍历所有节点，更新结果`res`为所有节点中的最大路径和。
  - `cout<<res<<endl;`：输出最终结果。
  - `return 0;`：程序结束。

这个代码是一个典型的树形DP应用，通过深度优先搜索遍历图，并计算每个节点的最大路径和。

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

十五月明

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

蓝桥杯2015年第六届真题-生命之树树形dp

评论区

精彩推荐

C二级辅导-分段函数（C语言代码）

点我有惊喜！你懂得！

简单的a+b （C语言代码）

C二级辅导-进制转换（C语言代码）

母牛的故事（C语言代码）

C语言训练-求函数值（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

众数问题（C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

单词个数统计（C语言代码）

十五月明

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

蓝桥杯2015年第六届真题-生命之树 树形dp

评论区

精彩推荐

C二级辅导-分段函数 （C语言代码）

点我有惊喜！你懂得！

简单的a+b （C语言代码）

C二级辅导-进制转换 （C语言代码）

母牛的故事 （C语言代码）

C语言训练-求函数值 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

众数问题 （C语言代码）

三角形 （C++代码）递归（存在大量重复计算，容易出现时间超限）

单词个数统计 （C语言代码）

蓝桥杯2015年第六届真题-生命之树树形dp

　　评论区

C二级辅导-分段函数（C语言代码）

C二级辅导-进制转换（C语言代码）

母牛的故事（C语言代码）

C语言训练-求函数值（C语言代码）

众数问题（C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

单词个数统计（C语言代码）