蓝桥杯15届第十题——生命之树（dfs， vector）

叁歲伎倆 2023-07-24 13:24 14阅读 0赞

前言：题目看似简单，但是对于第一次接触这类题型的同学还是会存在着一定的困难。  
这类题型是典型的**树型遍历**问题。若我们能够将树都按照路径遍历一遍，然后一直维护一个权值最大的子集即可。

## 生命之树题目 ##

在X森林里，上帝创建了生命之树。  
他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。  
上帝要在这棵树内选出一个非空节点集S，使得对于S中的任意两个点a,b，都存在一个点列 \{a, v1, v2, …, vk, b\} 使得这个点列中的每个点都是S里面的元素，且序列中相邻两个点间有一条边相连。  
在这个前提下，上帝要使得S中的点所对应的整数的和尽量大。  
这个最大的和就是上帝给生命之树的评分。  
经过atm的努力，他已经知道了上帝给每棵树上每个节点上的整数。但是由于 atm 不擅长计算，他不知道怎样有效的求评分。他需要你为他写一个程序来计算一棵树的分数。  
「输入格式」  
第一行一个整数 n 表示这棵树有 n 个节点。  
第二行 n 个整数，依次表示每个节点的评分。  
接下来 n-1 行，每行 2 个整数 u, v，表示存在一条 u 到 v 的边。由于这是一棵树，所以是不存在环的。  
「输出格式」  
输出一行一个数，表示上帝给这棵树的分数。  
「样例输入」  
5  
1 -2 -3 4 5  
4 2  
3 1  
1 2  
2 5  
「样例输出」  
8

--------------------

题目描述了一棵无根树，我们可以给树建立一个根，将树都按照路径遍历一遍，然后一直维护一个权值最大的子集即可。  
具体如下：  
①、一个节点走到下一个节点的路径是不定的，那我们如何存储路径？  
我们可以利用动态数组vector来存储路径信息。

vector <ll> g[MAXN+1]; //邻接表：记录相邻的结点
    					   //MAXN+1：节点数
    					   //g[a].size()：a节点对应的路径数

②、如何设计dfs？  
w数组：记录每个点的权重。  
ww数组：记录每个点作为根节点时能得到的最大权和。

首先，我们要选择一个节点作为树的起始根。  
第二，不断试探路径。若下一个结点最大权重大于0，则将下一个结点上的权重赋给结点。  
第三，记录最大的权和ans。

#include<bits/stdc++.h>
    #define ll long long 
    using namespace std;
    ll n;
    const ll MaxN=1e5;
    ll w[MaxN+1];			//每个点的权重 
    ll ww[MaxN+1];			//每个点作为根节点时能得到的最大权和
    ll ans=0; 
    vector <ll> g[MaxN+1];	//邻接表：记录相邻的结点，不确定相邻结点数
    
    /*以root为根，算出最大的权和*/
    void dfs(ll root, ll fa)	//无根树转有根树
    { 
    	ww[root]=w[root];		//节点初值 
    	
    	for(int i=0; i<g[root].size(); ++i)	//g[root].size()：与root相关的路径数 
    	{ 
    		ll son = g[root][i];	//其中一个孩子
    		if(son!=fa)				//防止返回 
    		{ 
    			dfs(son, root);		
    			if(ww[son]>0)		//以son为根的路径产生的和谐值大于0则保留，否则舍弃 
    			ww[root]+=ww[son];
    		}
    	}
    	if(ww[root]>ans) ans=ww[root];//保留路径产生最大的和谐值
    } 
    
    int main()
    { 
    	//输入 
    	cin>>n;
    	for(ll i=1; i<=n; i++)
    	cin>>w[i];
    	for(ll j=1; j<n; j++)	//n-1条路径 
    	{ 
    		ll u, v;
    		cin>>u>>v;
    		g[u].push_back(v);	//使用vector来存储来回路径 
    		g[v].push_back(u);	//双向
    	}
    	dfs(1, 0);		//将w[1]作为根
    	cout<<ans;
    	
    	return 0;
    }

希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白。