what is the approach being the ques named Corrouption in Freedonia( MINIKILL)

# MINIKILL - ENIGMA! EDITORIAL PLEASE!

I got WA.

My approach:

The value for a vertex is the sum of its children

If the vertex contains at least one child such that its branch has only 1 path in it, then subtract 1 from its value

All leaves are 1

I used the logic that we have two cases -whether to cut a particular node on which we are right now or not, and find the answer for both these cases for each node. When a node is not cut, the number of components we currently have will be always 1. Similarly there will be two cases for each of its children too. So if we want to cut a particular node, atleast one of the child nodes should also be cut. So I found the max value of a child, when cut will give us the maximum amount of different components. And for the other children we can use the max value of both cases (cut or not cut).

u have any good TC ??

Your logic is completely correct. There might be some flaws in your code.

My logic was the same as yours and this gives AC :

https://www.codechef.com/viewsolution/28873175

Testcase-1:

21

1 2

1 3

2 7

2 13

2 14

2 15

3 5

3 6

3 4

6 16

6 17

7 8

7 9

7 10

7 11

7 12

5 18

5 19

5 20

5 21

Test-case-2:

10

1 2

1 3

1 4

2 5

5 6

3 7

7 8

4 9

9 10

Hope it helps

My Submission Link https://www.codechef.com/viewsolution/28872164

Will u pls tell me what i m missing?

your Tcâ€™s are also working in my code:

I tried but canâ€™t find anything wrong till now. I have seen most people use dfs/bfs in tree-dp-problems, I use some weird method of traversal in which I start from leaves and eventually reach the root and it seems to work fine most of the times

When one gets to 6 star, are they supposed to write 400 line solutions

Stop it

pls if anyone has good Testcase so pls post it here :

9

1 2

2 4

2 3

2 5

1 6

6 7

1 8

8 9

Ans - 4

11

1 2

2 4

2 3

2 5

1 6

6 7

1 8

8 9

6 10

6 11

Ans - 5

I used these two to debug my code.

Thereâ€™s a huge difference between (6-star coders) and (6-star coders who only do long challenges)

One more important testcase I feel is the one which has many straight-paths in a tree.

ankit_betch you savage XD XD

can u explain what u did??and logic too

@naman_9899

Nhi yaar. Jaane do.Long challenge waalon ko kaha kuch coding aata hai . Sab long challenge waalein to stupid hi hai according to some coding-immortals here

are brooâ€¦ignore such foolsâ€¦meko pta h 6 star phuchna is not a cakewalk,i takes sleepless nightâ€¦apart from thisâ€¦soltuion btaa naaâ€¦i was thinking of the diameter or something like that for the quesâ€¦

just tell me the approach:slightly_smiling_face:

Haan bhaiâ€¦toh this is a very famous(self-created) trick , you gotta memorize it , ok ?

In tree-dp questions(most of them), you start from leaves and traverse till the root like this :-

Lets calculate answer for this :-

And this:-

If we join them both, answer is this:-

In short, from the bottom, go up and keep joining all the sums till you reach the root !