How to solve this problem from POI? It simply states: Given a tree find a triplet of nodes (a,b,c) such that distance between each other is same!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 165 |
2 | maomao90 | 163 |
2 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
How to solve this problem from POI? It simply states: Given a tree find a triplet of nodes (a,b,c) such that distance between each other is same!
Name |
---|
That's not what the problem is asking. It asks to compute the number of such triplets.
You can prove that for any such triplet, there must exist another vertex L which is between them in the tree (i.e., L-A, L-B, L-C forms a star-like shape), and the distances L-A, L-B, L-C must be equal. So you loop over every vertex L, then run DFS counting vertices at each distance. Gives O(n^2) runtime.
Won't that overcount? Like in the sample itself, the distance of nodes {4, 6, 7} are all 2 from the node 2, so we count them once, but then the nodes {4, 6, 7} are also at distance 1 from the node 5 and so we count them again. How do we account for this?
Right. You should only count triples which are in different branches of the tree going out of L. (Note that there may be Ω(n) of these branches, so you need to do that in a non-slow way.)
Check out this