I_love_Captain_America's blog

problemset/problem/543/D
By I_love_Captain_America, history, 9 years ago, In English

http://mirror.codeforces.com/problemset/problem/543/D

I did not understand the editorial so I wrote a solution of my own. But I don't understand the tricky cases where it fails. Here is my submission ID 11679268 . My logic is simple:

  1. Do DFS with "1" as root , store results in dp[i]

  2. result[1]=dp[1]

  3. result[i]=(1 + result[parent_of_i]/(dp[i]+1)) * dp[i] % mod;

Where is the logic wrong? I couldn't figure it out.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by I_love_Captain_America (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

This my code http://mirror.codeforces.com/contest/543/submission/11369630 — its Accepted

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

To divide result[parent_of_i]/(dp[i]+1) it's better to precalc prefix and suffix multiplications ans just calc something like pref[i-1]*suff[i+1]

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I calculate inverse power modulo 1000000007 in logarithmic time. I think I found the problem. If result[parent_of_i]==0, then all the further multiplication and division work goes to waste. I tried to work this out, but still haven't got it.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Still couldn't fix the bug when (result[parent_of_i]=0 and dp[i]=1000000006) . vintage_Vlad_Makeev can you please explain how prefix and suffix are calculated ?

→ Reply