CJOJ 2171 火車站開飯店（樹型動態規劃）
Description
政府邀請了你在火車站開飯店，但不允許同時在兩個相連的火車站開。任意兩個火車站有且只有一條路徑，每個火車站最多有 50 個和它相連接的火車站。
告訴你每個火車站的利潤，問你可以獲得的最大利潤為多少？
例如下圖是火車站網絡：
最佳投資方案是 1 ， 2 ， 5 ， 6 這 4 個火車站開飯店可以獲得的利潤為 90.
Input
第一行輸入整數 N(<=100000), 表示有 N 個火車站，分別用 1,2,……..,N 來編號。
接下來 N 行，每行一個整數表示每個站點的利潤，接下來 N-1 行描述火車站網絡，每行兩個整數，表示相連接的兩個站點。
Output
輸出一個整數表示可以獲得的最大利潤。
Sample Input
6
10
20
25
40
30
30
4 5
4 6
3 4
1 3
2 3
Sample Output
90
Http
CJOJ:http://oj.changjun.com.cn/problem/detail/pid/2171
Source
樹型動態規劃
解決思路
這道題與POJ2342真是有異曲同工之妙，這里不再過多敘述，請參考這里
代碼
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;const int maxN=100001;
const int inf=2147483647;int n;
int Value[maxN];
vector<int> E[maxN];
int F[maxN][5]={0};
bool vis[maxN]={0};void dfs(int u);int main()
{int u,v;cin>>n;for (int i=1;i<=n;i++)scanf("%d",&Value[i]);for (int i=1;i<n;i++){scanf("%d%d",&u,&v);E[u].push_back(v);E[v].push_back(u);}dfs(1);cout<<max(F[1][1],F[1][0])<<endl;return 0;
}void dfs(int u)
{vis[u]=1;F[u][1]=Value[u];F[u][0]=0;for (int i=0;i<E[u].size();i++){int v=E[u][i];if (vis[v]==0){dfs(v);F[u][1]+=F[v][0];F[u][0]+=max(F[v][1],F[v][0]);}}return;
}
