Блог пользователя Sammmmmmm

Pudding Monster but on a tree :))
Автор Sammmmmmm, история, 4 месяца назад, По-английски

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 месяца назад, # |
← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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$$$)]);

→ Ответить
»
4 месяца назад, # |
← Rev. 7   Проголосовать: нравится +14 Проголосовать: не нравится

incorrect solution

→ Ответить