SUBMEXS - Editorial

editorial
, , , , , ,
8

@bootcoder

9

I did dp on trees.

void dfs(ll u, ll p)
{
    par[u] = p;
    cnt[u] = 1;
    for (int v : adj[u])
    {
        if (v != p)
        {
            dfs(v, u);
            cnt[u] += cnt[v];
        }
    }
    if (adj[u].size() == 1 && u != 1) dp[u] = 1;
    for (int v : adj[u])
        if (v != p)
            ckmax(dp[u], dp[v]+cnt[u]);
}

dp_i is the answer for the subtree of i including i.
So dp_u = \text{max}(dp_v) \ + \ \text{size}(u)

5 Likes
10

thanks!

11

Hello, can anyone tell me what I’m doing wrong?
My solution
What the code is doing is that it calculates how many vertices there are in the subtree of each node and then it finds the vertex with maximum depth and does up the tree from that vertex until we reach vertex 1
At every vertex that we visit, we add (number of vertices in subtree) to the answer
Why I thought this was correct:
1
/\
2 3
/\
4 5
If we assign 0 to 5 then 1 to 4 and then 2 to 2 then 3 to 3 and then 4 to 1 then answer will be (1 + 3 + 5) = 9
Please help me ;-;

1 Like
12

My solution is
1.Calculate maximum size subtree for every level ,Let it be maxSiz[i] for level i , for e.g. maxSiz[1]=n 2. Then sum all the maxSiz[i] for all the levels,
Result is answer.

But it is giving wrong answer, i can’t think of any test case that fails, please point out the mistake, or just provide a test case.

My solution

13

When i submitted in cpp : CodeChef: Practical coding for everyone it passed but earlier i tried to submit in python the same code :: CodeChef: Practical coding for everyone i got runtime error i dont know why
please help

14

Try this testcase, ur code is giving wrong ans with this testcase.

3 Likes
15

how much time ur solution took? execution time?
I used dfs twice it took 0.20 secs.
https://www.codechef.com/viewsolution/39250093

1 Like
16

u should assign 1 to the leaf nodes and then calculate subtree size.
This is my submission link check this out
https://www.codechef.com/viewsolution/39250093

2 Likes
17

0.08s.

2 Likes
18

nice I m studying ur solution

1 Like
19

There’s some unnecessary stuff like par that I forgot to remove, so don’t confuse yourself.

2 Likes
20

use dfs twice

1 Like
21

Can you help me how the answer is 23.

22

First construct the tree as given. Then try to find out. But then please also help me with my solution.

23

Can anyone help me please??

24

My solution is

  1. Find all the leaves
  2. Find the number of immediate children nodes for each node
  3. Go from leaf to root and recursively add number of immediate children for current node+1 for each node coming in the path from leaf to root.
  4. find the maximum possible recursive addition for every leaf.
    Result is answer.

But it is giving wrong answer, i can’t think of any test case that fails, please point out the mistake, or just provide a test case.

My solution link:
https://www.codechef.com/viewsolution/39229234

25

https://www.codechef.com/viewsolution/39250093
see it

1 Like
28

My approach:

Calculate and store the size of subtree for each node. Initialize DP array.

dp[1] = subtreeSize[1]

Starting from root node, start BFS:

dp[children] = dp[parent] + subtreeSize[children]

The answer will be maximum of the DP array.

My solution in Java: https://www.codechef.com/viewsolution/39223219

29

I have also the same problem. I checked with an AC code, answer was 23 only. Now figuring out why?