I know about centroid decomposition but I cannot understand the solution given on USACO guide...Can someone please give a simple explanation to this problem https://cses.fi/problemset/task/2080
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I know about centroid decomposition but I cannot understand the solution given on USACO guide...Can someone please give a simple explanation to this problem https://cses.fi/problemset/task/2080
Name |
---|
Auto comment: topic has been updated by Pawan_Lahoti (previous revision, new revision, compare).
We are exploiting the fact that for any two nodes (u,v), the lca in their centroid tree divides it into two disjoint paths.
Thus when we find a centroid, we effectively want to calculate the summation of cnt_i[x] * cnt_j[y] where cnt_i denotes the cnt of depth = x in child i of centroid and x + y == k. Because of the above mentioned fact, we won't get any repetition.
Time complexity: for each layer of centroids , we will do O(N) operations and because the height of centroid tree is limited to log(N), Time Complexity will be O(Nlog(N)).