Warning: session_start(): open(/tmp/sess_42d896e11045b3fed86a8e05db4ef2b0, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/4/43994124a9168f34c03db2ff7cd35d94.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
[[http://poj.org/problem?id=2486|POJ 2486]]
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
int res,n,k,f[105][205][2],head[105],cnt,w[105],pa[105];
struct Node{int nxt,to;}Edges[105*2];
void addedge(int u,int v)
{
Edges[++cnt].nxt=head[u];
head[u]=cnt,Edges[cnt].to=v;
}
void dfs(int u)
{
f[u][0][0]=f[u][0][1]=w[u];
for(int i=head[u];~i;i=Edges[i].nxt)
{
int v=Edges[i].to;
if(pa[u]==v)continue;
pa[v]=u,dfs(v);
for(int j=k;j;j--)
{
for(int l=0;l<=j;l++)
{
if(j-l-2>=0)f[u][j][0]=max(f[u][j][0],f[u][l][0]+f[v][j-l-2][0]);
if(j-l-1>=0)f[u][j][1]=max(f[u][j][1],f[u][l][0]+f[v][j-l-1][1]);
if(j-l-2>=0)f[u][j][1]=max(f[u][j][1],f[u][l][1]+f[v][j-l-2][0]);
if(u==1)res=max(res,max(f[u][j][0],f[u][j][1]));
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
cnt=0;
memset(head,-1,sizeof(head));
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i