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
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | ecnerwala | 3654 |
3 | jiangly | 3627 |
4 | jqdai0815 | 3620 |
5 | orzdevinwang | 3612 |
6 | Benq | 3586 |
7 | Radewoosh | 3582 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3474 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 163 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | atcoder_official | 155 |
5 | maroonrk | 152 |
6 | -is-this-fft- | 148 |
6 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 145 |
10 | cry | 144 |
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
Название |
---|
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$$$)]);
nice bbc
Someone already replied but here is my incoherent solution:
Let us iterate over the smallest node $$$u$$$ in a valid subgraph in decreasing order.
Define $$$f(u, v), u \leq v $$$ to be a boolean variable which indicates whether the set of nodes from $$$u$$$ to $$$v$$$ form a connected subgraph. Let's assume that we know all $$$v$$$ such that $$$f(u + 1, v) = 1$$$. Now, we want to find every node $$$w : f(u, w) = 1$$$.
Firstly, let's find the maximum node $$$mx$$$ on the path from $$$u$$$ to $$$u + 1$$$. Notice that for all $$$v < mx : f(u, v) = 0$$$. Further, for all $$$v \geq mx, f(u + 1, v) = 1 \implies f(u, v) = 1$$$.
Now, we will also have some $$$v \geq mx : f(u + 1, v) = 0, f(u, v) = 1$$$. For the sake of brevity, we define a set $$$S$$$ which contains all such $$$v$$$. Finding $$$S$$$ efficiently is the crux of the problem.
We make the following observations:
Thereafter, we find the answer in the following manner:
This gives us a $$$O(n \log(n))$$$ solution.