题目:

国家探险队长 Jack 意外弄到了一份秦始皇的藏宝图,于是,探险队一行人便踏上寻宝之旅,去寻找传说中的宝藏。

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

注意:在整个过程中,每个人最多只能开采一个点的宝藏。

输入格式

第 1 行有 2 个整数 n 和 m。其中 n 表示藏宝点的个数(1≤n≤100),m 表示探险队的人数(1≤m≤100)。

第 2 行是 n 个不超过 100 的整数,分别表示 1 到 n 每个点的宝藏价值。

接下来 n-1 行,每行两个数,x 和 y(1≤x,y≤n,x≠y),表示藏宝点 x 与 y 之间有一条路,数据保证不会有重复的路出现。

假设一开始探险队在点 1 处。

输出格式

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

样例数据 1

输入  []

输出

备注

【数据范围】
对 40% 的输入数据 :1≤n≤30;m≤12。
对 100% 的输入数据 :1≤n≤100;m≤100。

题解:

树形dp··多叉树转二叉树处理附加维分配问题···很像选课··不过注意dp的一些细节··

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<cctype>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=;
int father[N],son[N],brother[N],f[N][N][],first[N],next[N*],go[N*],tot,n,m,val[N];
inline int R()
{
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f;
}
inline void comb(int a,int b)
{
next[++tot]=first[a],first[a]=tot,go[tot]=b;
next[++tot]=first[b],first[b]=tot,go[tot]=a;
}
inline void dfs(int u,int fa)
{
for(int e=first[u];e;e=next[e])
{
int v=go[e];if(v==fa) continue;
father[v]=u;dfs(v,u);
}
}
inline void dp(int u,int k,int t)
{
if(f[u][k][t]!=-) return;
if(u==||k==) {f[u][k][t]=;return;}
f[u][k][t]=;
if(t==) //只有父亲节点有人驻守才能分开
{
for(int i=;i<k;i++) //该节点留一个人
{
dp(son[u],i,),dp(brother[u],k-i-,);f[u][k][t]=max(f[u][k][t],f[son[u]][i][]+f[brother[u]][k-i-][]+val[u]);
}
for(int i=;i<=k;i++) //该节点不留人
{
dp(son[u],i,),dp(brother[u],k-i,);f[u][k][t]=max(f[u][k][t],f[son[u]][i][]+f[brother[u]][k-i][]);
}
}
else //否则只能儿子节点走完或者兄弟节点走完
{
dp(son[u],k,);dp(son[u],k-,);dp(brother[u],k,);
f[u][k][t]=max(f[u][k][t],max(f[son[u]][k][],f[brother[u]][k][]));
f[u][k][t]=max(f[u][k][t],f[son[u]][k-][]+val[u]);
}
return;
}
int main()
{
//freopen("a.in","r",stdin);
memset(f,-,sizeof(f));
n=R(),m=R();int a,b;
for(int i=;i<=n;i++) val[i]=R();
for(int i=;i<n;i++) a=R(),b=R(),comb(a,b);
dfs(,);for(int i=;i<=n;i++) brother[i]=son[father[i]],son[father[i]]=i;
dp(son[],m,);
cout<<f[son[]][m][]<<endl;
return ;
}
05-11 19:39