When I solve the problem I have collided with WA on test 11. I saw this test. In this test Q == 4. But it must be equal 2. I think when Marat Bakirov made this test hi take not into consideration what "Q denotes amount of branches that should be preserved" but not "removed"! Please correct this test.

If n=q, you must output the amount of all the apples.


Edited by author 06.04.2004 21:00

What is the answer for this test?

4 1
1 2 1
2 3 0
2 4 0

Can i remove 0-branches from tree or not?

Why my program is wrong,who can help me.
  This is my program:
   var
  a:array [0..100,0..100] of longint;
  s,b:array [0..100] of longint;
  used:array [1..100] of boolean;
  i,j,m,n,q,l,k,ans:longint;
 procedure cal(k:longint);
  var
   i,j:longint;
  begin
   used[k]:=true;
   for i:=1 to n do
    if (a[k,i]<>-1) and (not used[i]) then
     begin
      cal(i);
      b[k]:=b[k]+b[i]+1;
      s[k]:=s[k]+s[i]+a[k,i];
     end;
  end;
 function del(k,m:longint):longint;
  var
   i,j,min,k1,k2,mink,ss,t:longint;
  begin
   if m=0 then begin
    del:=0;
    exit;
   end;
   used[k]:=true;
   if m=b[k]
    then del:=s[k]
    else begin
     k1:=0; k2:=0;
     for i:=1 to n do
      if (a[k,i]<>-1) and (not used[i]) then
       if k1=0 then k1:=i
               else k2:=i;
     min:=maxlongint;
     if m>b[k1] then min:=s[k1]+a[k,k1]+del(k2,m-b[k1]-1);
     if m>b[k2] then begin
      ss:=s[k2]+a[k,k2]+del(k1,m-b[k2]-1);
      if min>ss then min:=ss;
     end;
     for i:=m-b[k2] to b[k1] do begin
      ss:=del(k1,i);
      ss:=del(k2,m-i)+ss;
      if ss<min then min:=ss;
     end;
     del:=min;
    end;
   used[k]:=false;
  end;
 begin
  readln(n,q);
  for i:=0 to 100 do
   for j:=0 to 100 do
    a[i,j]:=-1;
  for k:=1 to n-1 do begin
   readln(i,j,l);
   a[i,j]:=l;
   a[j,i]:=l;
  end;
  fillchar(used,sizeof(used),false);
  cal(1);
  s[0]:=0; b[0]:=0;
  fillchar(used,sizeof(used),false);
  ans:=s[1]-del(1,n-q-1);
  writeln(ans);
 end.

This is my program, can anybody tell me what is wrong?
I did lot of tests and it seems to work, but I get WA.
pleeeeaaaasssssseeeeeee, help!!!!!

#include <iostream.h>
#include <fstream.h>

#ifndef ONLINE_JUDGE
ifstream in("in.txt");
ofstream out("out.txt");
#else
#define in cin
#define out cout
#endif

int max(int a,int b)
{
    return a>b?a:b;
}

class PreNode
{
public:
    PreNode():_size(0){}
    Add(int n)
    {
        _branch[_size++] = n;
    }
    int _size;
    int _branch[3];
};

class Node
{
public:
    Node()
    {
        _child[0] = NULL;
        _child[1] = NULL;
    }
    int _apples;
    int _maxBranches;
    int _maxApples[101];
    Node *_child[2];
    void GetVect();
    void AddOneChild(Node *child)
    {
        _maxBranches = child->_maxBranches+1;
        for(int i = 0;i<=child->_maxBranches;i++)
            _maxApples[i+1] =
child->_maxApples[i]+_apples;
    }
};

PreNode preTree[101];
int apples[101][101];
Node tree[101];
int N,Q;

void Make(int n,int p)
{
    int hijo = 0;
    tree[n]._apples = apples[p][n];
    for(int i = 0;i<preTree[n]._size;i++)
    {
        if(preTree[n]._branch[i] != p)
        {
            tree[n]._child[hijo++] =
&tree[preTree[n]._branch[i]];
            Make(preTree[n]._branch[i],n);
        }
    }
}

void Node::GetVect()
{
    for(int h = 0;h<2;h++)
    {
        if(_child[h] != NULL)
            _child[h]->GetVect();
    }
    _maxApples[0] = _apples;
    if(_child[0] == NULL && _child[1] == NULL)
        _maxBranches = 0;
    else
    {
        if(_child[0] != NULL && _child[1] == NULL)
            AddOneChild(_child[0]);
        else
        {
            if(_child[1] != NULL && _child[0] ==
NULL)
                AddOneChild(_child[1]);
            else
            {
                _maxBranches =
2+_child[0]->_maxBranches+_child[1]->_maxBranches;
                for(int i = 1 ; i<=
_maxBranches;i++)
                {
                    int maxi = 0;

if(_child[0]->_maxBranches >= i-1)
                        maxi =
max(maxi,_child[0]->_maxApples[i-1]+_apples);

if(_child[1]->_maxBranches >= i-1)
                        maxi =
max(maxi,_child[1]->_maxApples[i-1]+_apples);
                    for(int j =
0;j<=i-2;j++)
                    {

if(_child[0]->_maxBranches >= j && _child[0]->_maxBranches
>= (i-2-j))
                        {
                            maxi
=
max(maxi,_child[0]->_maxApples[j]+_child[1]->_maxApples[i-2-
j]+_apples);

                        }
                    }
                    _maxApples[i] =
maxi;
                }
            }
        }
    }
}

int main()
{
    int i;
   in >> N;
   in >> Q;
   for(i=0;i<N-1;i++)
   {
       int f,t,m;
       in >> f >> t >> m;
       apples[f][t] = m;
       apples[t][f] = m;
       preTree[f].Add(t);
       preTree[t].Add(f);
   }

    tree[1]._apples = 0;
    Make(1,-1);
    tree[1].GetVect();
    out << tree[1]._maxApples[Q];
   return 0;
}

how q can equal to n??? :(

Though I know to Dp,but I really don't know the detail to
record.Can anyone send me a Tree Dp program?
Email:liuzhizhi@hotmail.com
Thanks a lot.

my email: yuwei110@yahoo.com.cn

830799 20:21:00
22 Apr 2005 nicushor 1018 C++ Accepted
 0.001 190 KB
:))

5 2
1 2 1
1 3 0
3 4 0
3 5 1


Is '1' (I think) or '2' ???

7 1
1 2 1
1 3 1
2 6 0
2 7 0
3 4 0
3 5 0
What should be the answer 1 or 2?

Edited by author 18.04.2005 02:30

In this board people have been discussing about not removing 0-apple branches. Now it's completely RUMOUR! Just do everything as usual.

If you get WA #11, it's because your algo is wrong. Greedy won't work. Use DP!

Please,please,I am crazy

I got WA in the 11th data, and I've readen the discussion in the webboard, but them made me even more puzzled. What should I do with the branch which is 0 on earth? And what about when n=q? Would you please help me?
And this is my program, I will be very thankful if you can tell me what's wrong with my program too.
First, I use e and cost to record the nodes and numbers of apples. Then I build up a tree, delete the branch which is on the top and with the fewest apples. When k=n-1-m, the answer comes out.
As follow:
type aas=record
     bef:shortint;
     val:integer;
     nex:array[1..2]of byte;
end;
var i,j,k,t,n,m,a,b,c:integer;
    ans:longint;
    tree:array[1..100]of aas;
    e:array[1..100,1..3]of shortint;
    cost:array[1..100,1..3]of integer;
    num:array[1..100]of shortint;
    mark:array[1..100]of shortint;

procedure find(aa:integer);
var i2:integer;
begin
     for i2:=1 to num[aa] do if mark[e[aa,i2]]=0 then begin
         inc(mark[aa]);
         tree[aa].nex[mark[aa]]:=e[aa,i2];
         tree[e[aa,i2]].bef:=aa;
         tree[e[aa,i2]].val:=cost[aa,i2];
     end;
     for i2:=1 to mark[aa] do find(tree[aa].nex[i2]);
end;

begin
     readln(n,m);
     fillchar(e,sizeof(e),0);
     fillchar(num,sizeof(num),0);
     fillchar(cost,sizeof(cost),0);
     ans:=0;
     for i:=1 to n-1 do begin
         read(a,b);
         readln(c);
         if c>0 then begin
            inc(num[a]);
            inc(num[b]);
            e[a,num[a]]:=b;
            e[b,num[b]]:=a;
            cost[a,num[a]]:=c;
            cost[b,num[b]]:=c;
            ans:=ans+c;
         end;
     end;
     fillchar(tree,sizeof(tree),0);
     fillchar(mark,sizeof(mark),0);
     find(1);
     k:=0;
     while k<n-1-m do begin
           c:=-1;
           for i:=1 to n do if (mark[i]=0)and((c=-1)or(c>tree[i].val)) then begin
               c:=tree[i].val;
               t:=i;
           end;
           inc(k);
           mark[t]:=-1;
           ans:=ans-c;
           dec(mark[tree[t].bef]);
     end;
     writeln(ans);
end.

1) There are some branches which have 0 apples. Every such branch
does NOT contain any non-zero branch - this test is impossible:
5 2
1 2 1
1 3 0
3 4 0
3 5 1,
because branch 3 (with 0 apples) contains branch 5 (with 1 apple).

2) If there are some branches with 0 apples, we should IGNORE them
and left from other branches (q - number of zero branches) ones. See
also 1).
For example,
7 5
1 2 1
1 3 0
3 4 0
3 5 0.
2 6 0
2 7 1
There are 4 zero branches. Ignore them - you'll get 2 branches.
1 2 1
2 7 1
From these branches you should left 5(q) - 4(number of zero
branches) = 1 branch. Remove 2 7 1 and you'll get answer: 1.

3) All tests are correct now, but for this problem sometimes I had
Wrong Answer, but it should be Runtime Error.

Hi
Can you Answer These Test Cases?
I know these are too much but please help me :(( I can`t understand
what programme should do with 0-apple branches :(
Can you tell me What Should we do with branches contain 0 apple?
Also If we should preserve or Cut them at first, then it might we
get forced by q... For example if we have 4 0-apple and 1 non-0-apple
branche then what should we do for q=2 or q=3 ?
Best Regards
Aidin_n7@hotmail.com

Test #1:
6 2
1 2 10
1 4 30
2 3 0
4 5 0
4 6 100

Test #2:
6 2
1 2 10
1 4 30
2 3 0
4 5 0
4 6 0

Test #3:
7 4
1 2 10
2 4 10
2 5 0
1 3 0
3 6 10
3 7 10

Test #4:
5 3
1 2 10
2 3 0
2 4 0
1 5 0

Test #5:
5 2
1 2 10
2 3 0
2 4 0
1 5 0

Test #6:
7 1
1 2 0
1 5 0
2 3 10
2 4 10
5 6 10
5 7 10

Test #7:
7 2
1 2 0
1 5 0
2 3 10
2 4 10
5 6 10
5 7 10

Test #8:
7 3
1 2 0
1 5 0
2 3 10
2 4 10
5 6 10
5 7 10

With The Best Wishes
Aidin_n7