树形DP例2

题面描述

给定一颗n个点的点权树，问树中每个子树的点权和，点权最大值。n≤10^5

输入格式

第一行输入一个正整数n（2≤n≤10^5）;

第二行输入n个正整数d(1≤d≤2700000000),表示每点的权值。

第三行到第n+1行输入每条边的信息，每行输入两个整数u（1≤u≤n）,v（1≤v≤n）。分别表示边的起点、终点。

数据保证输入的是一棵树。

输出格式

共两行; 第一行输出n个数,表示当前点所包含最大子树的点权和;

第二行输出n个数,表示当前点所包含最大子树的最大点权;

不过滤行末空格

样例

数据范围

感觉这个还是个树形DFS并不是DP的样子，这个题就是把统计边数变成了统计点权值而已，并没有什么本质算法的区别，还是要dfs，在回溯时加起来，维护一下最大值就好了。

代码

#include<bits/stdc++.h>
using namespace std;
long long  si[1001000],de[1001000],head[1001000],ver[1001000],ne[1001000],tot=0,a[1001000];
void add(int x,int y)
{
	ver[++tot]=y;
	ne[tot]=head[x];
	head[x]=tot;
 } 
void dfs(int x,int y)
{
	si[x]=a[x];
	de[x]=a[x];
	for(int i=head[x];i;i=ne[i])
	{
		if(ver[i]==y)
		continue;
		dfs(ver[i],x);
		de[x]=max(de[ver[i]],de[x]);
		si[x]+=si[ver[i]];
	}
}
int main()
{
	freopen("t20.in","r",stdin);
	freopen("t20.out","w",stdout);
	int n;
	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;
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	cout<<si[i]<<' ';
	cout<<endl;
	for(int i=1;i<=n;i++)
	cout<<de[i]<<' ';
	return 0;
}