题目描述

政府邀请了你在火车站开饭店，但不允许同时在两个相连接的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有50个和它相连接的火车站。
告诉你每个火车站的利润，问你可以获得的最大利润为多少。

输入格式 Input Format

第一行输入整数N(<=100000)，表示有N个火车站，分别用1，2。。。，N来编号。接下来N行，每行一个整数表示每个站点的利润，接下来N-1行描述火车站网络，每行两个整数，表示相连接的两个站点。

输出格式 Output Format

输出一个整数表示可以获得的最大利润。

输入：

6
10
20
25
40
30
30
4 5
1 3
3 4
2 3
6 4

输出：

90

---

想法

由于任意两个火车站有且只有一条路径，所以我们可以把其看做一棵树，每一个节点的状态是由其父亲节点决定，如果其父亲有饭店，呢就有一种选择，反之，就有两种选择；

我们可以开两个数组：F[i]与G[i]，分别表示第i个节点有饭店与无饭店所得的最优值，由此列出状态转移方程：
$ F[X]=\sum{i=1}^n G[y_i] $
$ G[i]= \sum{i=1}^n max(F[y_i],G[y_i]) (y_i是X的儿子) $

实现时用DFS去实现，每个点只需求一次，所以时间复杂度为O(N)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>
using namespace std;
struct ss{
	int y,next;
}e[200001];
long long Link[100001],tot=0,a[100001],b[100001]={},F[100001]={},G[100001]={};
long long n;
inline int insert(int xx,int yy)
{
	e[++tot].next=Link[xx];	e[tot].y=yy;	Link[xx]=tot;
}
inline int init()
{
	int x,y;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		insert(x,y);
		insert(y,x);
	}
}
void dfs(int child,int father)
{
	for(int i=Link[child];i!=0;i=e[i].next)
	{
		if(e[i].y!=father)
		{
			dfs(e[i].y,child);
			F[child]+=G[e[i].y];
			G[child]+=max(F[e[i].y],G[e[i].y]);
		}
	}
	F[child]+=a[child];
}
int main()
{	

	memset(e,0,sizeof(e));
	cin>>n;
	for(int i=1;i<=n;i++)		
        cin>>a[i];
	init();
	dfs(1,1);
	cout<<max(F[1],G[1])<<endl;
	return 0;
}