Description

探险队长凯因意外的弄到了一份黑暗森林的藏宝图，于是，探险队一行人便踏上了寻宝之旅，去寻找传说中的宝藏。 藏宝点分布在黑暗森林的各处，每个点有一个值，表示藏宝的价值。它们之间由一些小路相连，小路不会形成环，即两个宝藏点之间有且只有一条通路。探险队从其中的一点出发，每次他们可以留一个人在此点开采宝藏，也可以不留，然后其余的人可以分成若干队向这一点相邻的点走去。需要注意的是，如果他们把队伍分成两队或两队以上，就必须留一个人在当前点，提供联络和通讯，当然这个人也可以一边开采此地的宝藏。并且，为了节约时间，队伍在前往开采宝藏的过程中是不会走回头路的。现在你作为队长的助理，已经提供了这幅藏宝图，请你算出探险队所能开采的最大宝藏的价值。

Input

第一行有两个正整数n(1<=n<=100)，表示藏宝点的个数，m(1<=m=100)表示探险队的人数。 第二行是n个不超过100的正整数，分别表示1到n每个点的宝藏价值。 接下来的n-1行，每行两个数，x和y(1<=x,y<=n,x<>y)，表示藏宝点x,y之间有一条路，数据保证不会有重复的路出现。 假设一开始探险队在点1处。

Output

一个整数，表示探险队所能获得最大的宝藏价值。

Sample Input

5 3 1 3 7 2 8 1 2 2 3 1 4 4 5

Sample Output

16

思路

还是树形DP

设f[i][j][0..1]为第i个节点的子树，放了j个人，i之前是否选择过的最大价值。

转移还是非常easy的！

代码

#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int maxn=100077; vector<int> a[maxn]; int n,m,b[maxn],ass=0,ans=0,f[maxn][2],c[maxn]; void dfs(int u,int fa) { f[u][0]=1; f[u][1]=1; if(u<=n) f[u][!c[u]]=0x3f3f3f3f; for(int i=0; i<b[u]; i++) if(a[u][i]!=fa) { int x=a[u][i]; dfs(x,u); f[u][0]+=min(f[x][0]-1,f[x][1]); f[u][1]+=min(f[x][1]-1,f[x][0]); } } int main() { scanf("%d%d",&m,&n); // memset(f,sizeof(f),0x3f); for(int i=1; i<=n; i++) { int x; scanf("%d",&c[i]); } for(int i=1; i<=m-1; i++) { int x,y; scanf("%d%d",&x,&y); a[x].push_back(y); a[y].push_back(x); b[x]++; b[y]++; } // memset(d,0,sizeof(d)); dfs(n+1,0); printf("%d",min(f[n+1][0],f[n+1][1])); }