In FCTRE, I was getting WA for the first sub task when I used DFS . But why wouldn’t a simple DFS work here (for the first sub task ofcourse)?

maybe becoz u werent MOD-ding it

But according to the constraints, maximum happiness quotient possible is 10^9 (for the first sub task). What is the need to Mod?

I think you misinterpreted the question. Happiness quotient is the product of cost( A[i] ) in the path.

A[i] for all the subtasks is <=10^6. So product can exceed 10^9.

2 Likes

For the first subtask, N≤10^3

yes but node values a[i] had no such sub constraints… so products can be greater than mod(10e9+7)…

2 Likes

Ohh, yeah. I got confused too

1 Like

My bad. Thank you

If you want a video solution : Factor Tree - Mo's algorithm on Trees | Codechef April Long Challenge 2020 - YouTube