Just pay attention when Conviviality rating < 0.

Please, if you know, give an advice, how to pass this problem

Hint: DP on trees
Tutorial Link: https://codeforces.com/blog/entry/20935

If it is a real tree, why after N lines, describing conviviality ratings of employees,
we have not simply (N - 1) lines, describing supervisor relations?

Does such input format mean that some employees may have more than one supervisors?

Edited by author 21.06.2012 18:08

Why do I memory limit exceeded even if I have use pointer?
Here is my code:

const mn=6000;
      inf=-100000000;
type rec=record
           father:integer;
           num:integer;
           child:array[1..mn]of ^integer;
         end;
var value:array[1..mn]of ^integer;
    f:array[1..mn,1..2]of ^longint;
    t:array[1..mn]of ^rec;
    n,i,a,b,root:integer;
    ans:longint;

function max(a,b:longint):longint;
  begin
    if a>b
      then exit(a)
      else exit(b);
  end;

function dp(root,lab:integer):longint;
  var i:integer;
  begin
    if root=0 then exit(0);
    if f[root,lab]^>inf then exit(f[root,lab]^);
    if lab=1
      then begin
        f[root,lab]^:=value[root]^;
        for i:=1 to t[root]^.num do
          inc(f[root,1]^,dp(t[root]^.child[i]^,2));
      end
      else begin
        f[root,lab]^:=0;
        for i:=1 to t[root]^.num do
          inc(f[root,2]^,max(dp(t[root]^.child[i]^,1),dp(t[root]^.child[i]^,2)));
      end;
    exit(f[root,lab]^);
  end;

begin
  readln(n);
  for i:=1 to n do
    begin
      new(value[i]);
      new(t[i]);
      new(f[i,1]);
      new(f[i,2]);
      readln(value[i]^);
    end;
  while not eof do
    begin
      readln(a,b);
      if(a=0)and(b=0)then break;
      t[a]^.father:=b;
      inc(t[b]^.num);
      new(t[b]^.child[t[b]^.num]);
      t[b]^.child[t[b]^.num]^:=a;
    end;
  for i:=1 to n do
    if t[i]^.father=0
      then begin
        root:=i;
        break;
      end;
  for i:=1 to n do
    begin
      f[i,1]^:=inf;
      f[i,2]^:=inf;
    end;
  ans:=max(dp(root,1),dp(root,2));
  writeln(ans);
end.

Who can HELP me?

Edited by author 05.04.2010 16:57

Do not use signed char (C++) or signed byte (C#) to store convivality, or you get wrong results because of overflow.

The test 5 is:
7
1
1
100
100
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

After you sum 100 + 100, you get -56 in the signed char/signed byte variable, while the right sum should be 200.

Hope this helps.

Read the tutorial here : https://threads-iiith.quora.com/Dynamic-Programming-on-Trees-Tutorial

C++.  I was using recursive DFS. vector <vector<int> >.   I forgot to pass graph vector by reference and got MLE#8. After noticing that I am passing graph vector by value and simply adding an ampersand before vector name AC 1MB memory used.

Edited by author 03.07.2017 15:43

Any idea about this test?
I used Python2.7

my method is DP:
//invite
int sum = 0;
for (Integer c : guest.children) {
    sum += DP[c.intValue()][0];
}
DP[index][1] = sum + RATE[index];

// do not invite
sum = 0;
for (Integer c : guest.children) {
    int max = Math.max(DP[c.intValue()][0], DP[c.intValue()][1]);
    sum += max;
}
DP[index][0] = sum;



at first, I got WA on 13#,
DP the tree should from leaf to root,
but at first I sort the guests by its children count,
the right way is sort the guests by depth

Edited by author 25.07.2013 09:50

for each node v,calculate a(v)-maximum cost achieved by the subtree with root "v" in which v will attend, and n(v)-maximum cost achived by the subtree with root "v" in which v will not attend.
a(v)=p(v)+n(v1)+n(v2)+...+n(vn), vi-is the child of v.,p(v)-is the point of v itself.
n(v)=sum(max(n(vi),a(vi))),for all i-s.
and simply use DFS.

It is not clear at least 2 points:

1) "The output should contain the maximal total rating of the guests."
President is the host, not a guest, so his rating is excluded. (?)

2) As the party is the president's anniversary he cannot absent. (?)

Am i right? If not, correct the condition please.

My AC program on test
4
2
1
1
2
1 2
2 3
3 4
0 0
gives answer 3, but it seems to me that right answer is 4.
Please, check it

Wrong dfs:

    static void dfs(int i){

        used[i] = true;
        if (rank[i] > 0)goes[i] = rank[i];

        int sum_goes = 0, sum_dn_goes = 0;
        for (int to:T[i])
            if (!used[to]){
                dfs(to);
                sum_goes += goes[to];
                sum_dn_goes += dn_goes[to];
            }

        goes[i] = Math.max(goes[i], goes[i] + sum_dn_goes);
        dn_goes[i] += Math.max(sum_goes, sum_dn_goes);

    }


Right dfs:


    static void dfs(int i){
        used[i] = true;
        if (rank[i] > 0)goes[i] = rank[i];
        for (int to:T[i])
            if (!used[to]){
                dfs(to);
                goes[i] += dn_goes[to];
                dn_goes[i] += Math.max(goes[to], dn_goes[to]);
            }
    }

哈哈哈

First time I define array that max is 1600,so I crash.
But now I WA#14.
HELP!

Edited by author 15.07.2011 09:49

Edited by author 15.07.2011 09:50

Just dont forget:
1. The boss may not come to the party (I got WA many times because of this)
2. There may be nobody at the party

2
-2
-3
1 2
0 0
I don't know why I have a WA on 13th test(

Edited by author 11.08.2007 17:23