蓝桥杯生命之树（DFS）（JAVA）

朴灿烈づ我的快乐病毒、 2023-07-13 15:02 15阅读 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

##### 「样例输出」 #####

##### 「数据范围」 #####

对于 30% 的数据，n <= 10  
对于 100% 的数据，0 < n <= 10^5, 每个节点的评分的绝对值不超过 10^6 。

资源约定：  
峰值内存消耗（含虚拟机） < 256M  
CPU消耗 < 3000ms

#### 分析： ####

已知条件是一棵树，要求一部分节点构成的子集，且子集各个点之间是联通的  
就是说把原来的树删掉一部分子树（整体权重为负值），剩余的和就是答案

##### 以题中例子分五张图进行图解： #####

有五个点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]  
初始化五个点的值  
1 -2 -3 4 5  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]  
初始化四条边  
4 2  
3 1  
1 2  
2 5  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]

我们遍历寻找value最大的点，把他当作根  
然后把整个树以最大value为根梳理一下图示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]  
从底层向上迭代产生新的value值，  
value<=0不计数，  
最终计算根的value即为结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]  
ans=8；

#### DFS解法【语言受限：50%分】 ####

package JB2015;
    
    import java.util.ArrayList;
    import java.util.Scanner;
    //递归深度太深导致栈溢出
    //得分50%
    //java 限制递归最大一万层
    public class J生命之树递归 { 
    	public static long arr[],result;
    	public static ArrayList<Integer> tree[];
    	public static long dfs(int root,int fa){ 
    		long ans=arr[root];
    		for(int t:tree[root]){ 
    			if(t!=fa){ 
    				ans+=dfs(t,root);
    			}
    		}
    		return ans>0?ans:0;
    	}
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		int n=sc.nextInt();
    		arr=new long[n+1];
    		tree=new ArrayList[n+1];
    		long max=Integer.MIN_VALUE;
    		int index=-1;
    		tree[0]=new ArrayList();
    		for(int i=1;i<=n;i++){ 
    			tree[i]=new ArrayList();
    			arr[i]=sc.nextInt();
    			if(arr[i]>max){ 
    				max=arr[i];
    				index=i;
    			}
    		}
    		int u,v;
    		for(int i=1;i<n;i++){ 
    			u=sc.nextInt();
    			v=sc.nextInt();
    			tree[u].add(v);
    			tree[v].add(u);
    		}
    		result=arr[index];
    		for(int t:tree[index]){ 
    			result+=dfs(t,index);
    		}
    		System.out.println(Math.max(result,0));
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20230529/ccde67e94eae471e907b18a762f53946.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: /images/20230529/3a99042eaeb4401998193de32763f225.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: /images/20230529/f9a895494bf7457cbf8cee0ba3eada68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]: /images/20230529/a07f57f600c94f64a274d296711cb17e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]: /images/20230529/250dabd858544b83a0d9893566424e32.png