Sammmmmmm's blog

Pudding Monster but on a tree :))
By Sammmmmmm, history, 21 month(s) 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

»
21 month(s) ago, hide # |
← 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 \lt r$$$) such that $$$r - l$$$ = max(mx[ $$$l$$$ ..($$$r - 1$$$)]) — min(mn[ $$$l$$$ ..($$$r - 1$$$)]);

→ Reply
»
21 month(s) ago, hide # |
← Rev. 7  
Vote: I like it +14 Vote: I do not like it

incorrect solution

→ Reply
»
15 months ago, hide # |
← Rev. 3  
Vote: I like it +6 Vote: I do not like it

you can look into my algorithm, not sure if it's completely correct though

define $$$S(i)$$$ for $$$1\leq i \lt n$$$ as the set of nodes on the simple path between $$$i$$$ and $$$i+1$$$, $$$mn(i)$$$ and $$$mx(i)$$$ respectively the minimum and maximum index node in $$$S(i)$$$

obviously intervals of length 1 satisfy, we then need to count the number of pairs $$$(l,r)$$$ $$$(1\leq l \lt r\leq n)$$$ satisfying

$$$\min_{i=l}^{r-1} {mn(i)}\geq l$$$ and $$$\max_{i=l}^{r-1} {mx(i)}\leq r$$$

which can be done by precomputation and kquery here is the problem link (statement in vietnamese) and my implementation (which got ac) https://coder.husc.edu.vn/problem/olpicpc049c11e

https://ideone.com/GizYa3

sorry for the dirty code, hope you get the idea behind the algo

→ Reply