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

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

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.

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

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

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

Any idea about this test?
I used Python2.7

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

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

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.

 I mean the relationship between them is like a tree or a map?

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

TEST#4:
7
1
1
1
1
-128
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
TEST #7:
150
127
1
...(repeat for 149 times)
2 1
..
150 1

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.

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

My code:

type graph=^node;
    node=record v:longint;next:graph;end;
var g:array[1..6000] of graph;
    f:array[1..6000,0..1] of longint;
    a,deg:array[1..6000] of longint;
    n:longint;
function max(a,b:longint):longint;
begin
    if a<b then exit(b) else exit(a);
end;
procedure init;
var i,x,y:longint;
    p:graph;
begin
    read(n);
    for i:=1 to n do read(a[i]);
    repeat
     read(x,y);
     if (x<>0) or (y<>0) then
      begin
      new(p);inc(deg[x]);
      p^.v:=x;p^.next:=g[y];g[y]:=p;
      end;
    until (x=0) and (y=0);
    fillchar(f,sizeof(f),0);
end;
function search(v,x:longint):longint;
var p:graph;
    i:longint;
begin
        if f[v,x]<>0 then exit(f[v,x]);
        if x=1 then f[v,x]:=a[v];
        p:=g[v];
    if x=0 then
          begin
          while p<>nil do
            begin
            f[v,x]:=f[v,x]+max(search(p^.v,0),search(p^.v,1));
            p:=p^.next;
            end;
          end
        else begin
             while p<>nil do
               begin
               f[v,x]:=f[v,x]+search(p^.v,0);
               p:=p^.next;
               end;
             end;
        exit(f[v,x]);
end;
procedure work;
var i,j,c,ans,k:longint;
begin
        ans:=0;
    for i:=1 to n do
      if deg[i]=0 then
             inc(ans,max(search(i,0),search(i,1)));
        writeln(ans);
end;
begin
    init;
    work;
end.