Sammmmmmm's blog

Pudding Monster but on a tree :))
By Sammmmmmm, history, 4 months ago, In English

Given a tree of n vertices, count the number of ways to choose a connected subgraph of the tree so that all the vertices in that

subgraph consists of consecutive integers when sorted. Thanks!

N <= 3e5

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

»
4 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

let mx[i] = largest vertice on the path ($$$i, i + 1$$$).

mn[i] = smallest vertice on the path ($$$i, i + 1$$$).

calculate number of pairs ($$$l < r$$$) such that $$$r - l$$$ = max(mx[ $$$l$$$ ..($$$r - 1$$$)]) — min(mn[ $$$l$$$ ..($$$r - 1$$$)]);

→ Reply
»
4 months ago, # |
← Rev. 7   Vote: I like it +14 Vote: I do not like it

incorrect solution

→ Reply