我不是张玉想

用户名：ZYX666

访问量：5832

签　名：

---------------------------靓仔靓铝分割线---------------------------

等　　级
排　　名	699
经　　验	3926
参赛次数	8
文章发表	13
年　　龄	0
在职情况	学生
学　　校	东华理工大学
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

我不是张玉想——等差数列-题解（三个平台数据都可AC，原来的是错解，现已更新）
浏览：532

我不是张玉想——奇怪的数列-题解（C++代码）
浏览：277

我不是张玉想——数列分段-题解（C++代码）单纯为了抢沙发
浏览：265

你可能喜欢

我不是张玉想——生命之树-题解（C++代码）

　　作者: 我不是张玉想　　　　发表时间：2020-08-28 19:02:10 浏览：689　|　评论：0　

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

## 一、解题思路：
#### 树形DP
## 二、完整代码（仅供参考，欢迎提出建议和指正）
```cpp
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<vector>
#include<deque>
#include<set>
#include<stack> 
#include<cmath>
#include<time.h>
#include<iomanip>
using namespace std;
typedef long long int ll;

ll const maxn = 1e5+2;
ll ans=0;//这种初始化在本网站可以通过，其他网站需要初始化为-1e6
ll n;
ll value[maxn]={0};
vector<ll> line[maxn];//数组，每个元素是一个向量，类似邻接表

//第二个参数有用，防止父节点和子节点深搜时发生死循环
void dfs(int from,int ban){
	for(ll i=0;i<line[from].size();i++){//访问子节点
		if(line[from][i]!=ban){
			dfs(line[from][i],from);//这两个参数的作用是深搜访问from的子节点，在把from传下去，告诉下面的过程不能再返回来访问父节点（ban有禁止的意思）
			if(value[line[from][i]]>0){//from所有子节点的最大结果已经保存在value里了，如果还小于0，那也就没必要加上去了
				value[from]+=value[line[from][i]];
			}
		}
	}
	ans=max(ans,value[from]);//把过程中出现的最大值更新给ans
}

int main()
{
	cin>>n;
	for(ll i=1;i<n+1;i++){
		cin>>value[i];
	}
	int from,to;
	for(ll i=1;i<n;i++){//构建邻接表
		cin>>from>>to;
		line[from].push_back(to);
		line[to].push_back(from);
	}
	dfs(from,0);
	cout<<ans;
	return 0;
}
```
## 三、关于测试数据（欢迎讨论）
#### 代码中用于保存最终结果的变量ans的初始化存在一些小问题，我在三个平台用不同方式提交了代码（竞码编程、ACWing、C语言网）
####  竞码编程：ans=0、ans=-1e6都可以通过
####  ACWing：ans=0答案错误、ans=-1e6可以通过
####  C语言网：ans=0可以通过、ans=-1e6正确89%
#### 欢迎讨论，带佬们！！！！！！！！
##### PS：以上为本人拙见，若有错误或更好的方法，望大家不吝赐教，共同进步，十分感谢！！！

0.0分

4 人评分

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

我不是张玉想

TA的其他文章

你可能喜欢

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

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

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

C语言训练-邮票组合问题* （C语言代码）

不容易系列2 （C语言代码）

我不是张玉想——生命之树-题解（C++代码）

评论区

精彩推荐

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

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

川哥的吩咐（C语言代码）

C二级辅导-同因查找（C语言代码）

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

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

1009题解

printf基础练习2 （C语言代码）

循环入门练习6 （C语言代码）

交换Easy （C语言代码）

我不是张玉想

TA的其他文章

你可能喜欢

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

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

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

C语言训练-邮票组合问题* （C语言代码）

不容易系列2 （C语言代码）

我不是张玉想——生命之树-题解（C++代码）

评论区

精彩推荐

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

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

川哥的吩咐 （C语言代码）

C二级辅导-同因查找 （C语言代码）

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

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

1009题解

printf基础练习2 （C语言代码）

循环入门练习6 （C语言代码）

交换Easy （C语言代码）

　　评论区

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

川哥的吩咐（C语言代码）

C二级辅导-同因查找（C语言代码）