i have a test:
5 2
1 2 1
1 4 20
1 5 20
2 3 10
i think answer is 21 but my AC code answer is 40
maybe i wrong???

Hello! Can somebody tell me if there is a faster algo than O(Q^2*N)? My algo works pretty fast, but I wondered if there is a better way to do it.

can anyone please explain what test case 5 is  i have tried many times but iam not able to pass it

Hi, guys!
Can't move throw #11 test. Need help.
I just have build tree, and in every step removing smallest leaf.
At last, I count sum of left leaf's weight and print it.
But, algorithm don't pass at #11 test.
Thanks

Edited by author 21.10.2013 22:17

I guess there is a test case that the condition 1<=Q<=N-1 is not satisfied.
I put a condition that if Q is outside the given interval then output 0 and got WA#1.
Without this condition, it gives WA#8.

Edited by author 18.04.2013 20:01

Can anyone please tell me what is test case #5....My code is giving the correct ans for all the tests in the forum..

# include <stdio.h>
# include <algorithm>

using namespace std;

struct daw
{
    long long rg,lf,nd,vl,mx;
};

long long a,b;

long long w[409];
long long c[409][5];
long long v[409][409];

daw d[409];

void btr(long long x)
{
    if(d[x*2+1].vl!=0)
    btr(x*2+1);

    if(d[x*2+2].vl!=0)
    btr(x*2+2);

    if(x!=0)
    d[(x-1)/2].nd=d[(x-1)/2].nd+d[x].nd+1;
}

long long dp(long long x, long long y)
{
//    prlong longf("%d %d",x,y);getchar();

    if(y==0)
    return 0;

    if(v[x][y]>0)
    return v[x][y];

    for(long long i=0;i<=y;i++)
    if(d[x].nd-d[x*2+2].nd>=i && d[x*2+1].vl>0 && d[x*2+2].vl>0)
    {
        long long q=0;

        if(i!=0)
        q+=d[x].lf;

        if(i!=y)
        q+=d[x].rg;

        if(i==0)
        v[x][y]=max(v[x][y],dp(x*2+2,y-1)+q);

        else if(i==y)
        v[x][y]=max(v[x][y],dp(x*2+1,y-1)+q);

        else
        v[x][y]=max(v[x][y],dp(x*2+1,i-1)+dp(x*2+2,y-i-1)+q);
    }

    return v[x][y];
}

int main()
{
    scanf("%lld %lld",&a,&b);

    for(long long i=0;i<a-1;i++)
    scanf("%lld %lld %lld",&c[i][0],&c[i][1],&c[i][2]);

    d[0].vl=1;
    w[1]=1;

    for(long long i=0;i<a-1;i++)
    for(long long j=0;j<a-1;j++)
    {
        if(d[i].vl==c[j][0] && w[c[j][1]]==0)
        {
            if(d[i*2+1].vl==0)
            {d[i].lf=c[j][2];  d[i*2+1].vl=c[j][1];}

            else
            {d[i].rg=c[j][2];  d[i*2+2].vl=c[j][1];}

            w[c[j][0]]=1;
        }

        if(d[i].vl==c[j][1] && w[c[j][0]]==0)
        {
            if(d[i*2+1].vl==0)
            {d[i].lf=c[j][2];  d[i*2+1].vl=c[j][0];}

            else
            {d[i].rg=c[j][2];  d[i*2+2].vl=c[j][0];}

            w[c[j][0]]=1;
        }
    }

    btr(0);

    if(b==1)
    {printf("%lld",max(d[0].rg,d[0].lf));return 0;}

    printf("%lld",dp(0,b));

    getchar();
    getchar();
}


Thanks

found my mistake


Edited by author 26.06.2012 01:56

First move apples to point...
like the sample :
5 2
1 3 1
1 4 10
2 3 20
3 5 20
apple[3]=1 , apple[4]=10 , apple[2]=10 , apple[5]=10..

dp [ f ] [ j + i ] = Max( dp [ f ] [ j + 1 ] ,dp [ f ] [ j ] + dp [ h ] [ i ] +apple [ h ] )

dp [ k ] [ i ] means k is a tree's root,it has i lines..gets the max value...
" f " is h's father...just like this...from leaf to root to update the value..
in the end,print the answer: dp [ 1 ] [ q + 1 ]


Edited by author 25.09.2011 10:11

Let C[i][j] be weight of the edge( i, j). A( n, k ) - maximal amount of apples under k-th node after n cuts. B(k) - amount of edges under k-th node. Then ( k+ - right child and k-  - left child of the k-th nod )

A(n,k) = max{ a(n - B(k-), k+ ), if ( n > B(k-))                              }
            { a(n - B(k+), k- ), if ( n > B(k+))                              }                                                                           .           { MAX i FROM( 0) TO (n) OF a(n-i,k+)+a(i,k-) + C[k][k-]+C[k][k+]  }
            { A(0,k+) + A(0, k- ) + C[k][k-]+C[k][k+], if n = 0               }
            { - MAXAMOUNTOFAPPLES, if (k+ or k- doesn't exist AND n>0)        }

1-th and 2-th lines: one can cut left or rigth edge, if so we have to cut n-B(k+-) edges in the other subtree.

3-th line:           one can save both left and right edges, if so we have to cut i edges in left and n-i edges in the rigth subtrees. Choose maximal value changing i variable.

4-th line:           in this case we should count amout of apples under k-th node. It's equal to amount of apples in subtrees plus edge weights.

5-th line:           k is a leaf. if n>0 there is nothing to cut => deny this situation by MAXAMOUNTOFAPPLES with negative sign. I used MAXAMOUNTOFAPPLES  = 3000000

After that -  DP.

I just can not understand......

Edited by author 27.01.2011 11:40

When Q = N-1 you shouldn't remove any branch. I don't know why, but it works and my application was accepted. Otherwise you will get WA #1.

#include<iostream>
using namespace std;
const int maxn=105;
int count[maxn]; int g[maxn][maxn]; int n;int q; int cost[maxn][maxn]; int f[maxn][maxn]; int visit[maxn];
void init( )
{
            cin>>n>>q;
            for(int i=1;i<n;i++)
            {
                        int a,b,c;
                        scanf("%d %d %d",&a,&b,&c);
                        g[a][++count[a]]=b;
                        cost[a][b]=c;
                        g[b][++count[b]]=a;
                        cost[b][a]=c;
            }
            //memset(f,-10000,sizeof(f));
}
void dfs(int x)
{
            visit[x]=1;
            if(count[x]==0)
            {

                        return ;
            }
            for(int i=1;i<=count[x];i++)
            {
                        int child=g[x][i];
                        if(visit[child]==0){
                                    dfs(child);
                        for(int j=q;j>=0;j--)
                                    for(int k=q-j-1;k>=0;k--)
                                    {
                                                f[x][k+j+1]=max(f[child][k]+f[x][j]+cost[x][child],f[x][k+j+1]);

                                    }
                        }
            }
}
void print( )
{
            cout<<f[1][q]<<endl;
}
int main( )
{
            freopen("in.txt","r",stdin);
            init( );
            dfs(1);
            print( );
            return 0;
}

I got TL#6.

After that just a little bit updated my solution:

int max( int pos, int len )
{
..if ( ch[pos][len] )
....return dp[pos][len];
---
....ch[pos][len] = 1;
....dp[pos][len] = res;
....return res;
---
}

and got AC in 0.015s.

Edited by author 23.03.2010 20:30

I used DP tree,but i got TLE on #9,who can help me？
Here is my program:

program ural1018;
var
  a,b,c,n,q,i,j:longint;
  l,r,tot:array[0..100] of longint;
  map,f:array[0..100,0..100] of longint;
  use:array[0..100] of boolean;
procedure setup(v:longint);
var
  i:longint;
begin
  for i:=1 to n do
  if (map[v,i]<>-1)and(not use[i]) then
  begin
    if l[v]=0 then l[v]:=i else
    if r[v]=0 then r[v]:=i;
    use[v]:=true;
    setup(i);
  end;
end;
procedure ready(v:longint);
begin
  if l[v]<>0 then begin inc(tot[v]);ready(l[v]);end;
  if r[v]<>0 then begin inc(tot[v]);ready(r[v]);end;
  tot[v]:=tot[v]+tot[l[v]]+tot[r[v]];
end;
procedure dp(v,q:longint);
var
  i,x:longint;
begin
  if q=0 then exit;
  if l[v]>0 then
  begin
    if (q-1<=tot[l[v]])and(q-1>=0) then
    dp(l[v],q-1);
    if f[v,q]<f[l[v],q-1]+map[l[v],v] then
    f[v,q]:=f[l[v],q-1]+map[l[v],v];
  end;
  if r[v]>0 then
  begin
    if (q-1<=tot[r[v]])and(q-1>=0) then
    dp(r[v],q-1);
    if f[v,q]<f[r[v],q-1]+map[v,r[v]] then
    f[v,q]:=f[r[v],q-1]+map[v,r[v]];
  end;
  if (l[v]>0)and(r[v]>0) then
  for i:=0 to q-2 do
  if (i<=tot[l[v]])and(q-i-2<=tot[r[v]])and(q-i-2>=0) then
  begin
    dp(l[v],i);
    dp(r[v],q-i-2);
    if f[v,q]<f[l[v],i]+f[r[v],q-i-2]+map[v,l[v]]+map[v,r[v]] then
    f[v,q]:=f[l[v],i]+f[r[v],q-i-2]+map[v,l[v]]+map[v,r[v]];
  end;
  if (l[v]=0)and(r[v]=0) then f[v,q]:=0;
end;
begin
  readln(n,q);if q>=n-1 then q:=n-1;
  for i:=1 to n do
  for j:=1 to n do map[i,j]:=-1;
  while not eof do
  begin
    read(a,b,c);
    map[a,b]:=c;
    map[b,a]:=c;
  end;
  setup(1);
  ready(1);
  dp(1,q);
  write(f[1,q]);
end.

Edited by author 09.11.2010 02:50

Edited by author 09.11.2010 02:49

According to the problem's statement q<=n, and the number of branches is equal to n-1. Let's suggest q=n. In this case, how we can save n branches, if there number of is n-1?

Edited by author 29.07.2008 17:03