Hello CodeForces, today I tried solving the problem from a recent contest: [problem:1923E]↵
↵
My Solution: ↵
↵
<spoiler summary="Solution">↵
Use centroid decomposition to count the paths, for a given centroid, we keep track of the nodes we see first with a certain color and count the paths accordingly. Because colors go from 1 to N, we can use array instead of map. So I figured the time complexity would be O(N lg N). But the solution TLE's.↵
</spoiler>↵
↵
If you see any problems with the code, please let me know as I can't see the problem. If you don't understand a part of the code, please ask and I will clarify.↵
↵
Submission: [submission:255437477]↵
↵
UPD: The runtime takes more than 30 seconds! So I guess the runtime is O(N^2) somehow.
↵
My Solution: ↵
↵
<spoiler summary="Solution">↵
Use centroid decomposition to count the paths, for a given centroid, we keep track of the nodes we see first with a certain color and count the paths accordingly. Because colors go from 1 to N, we can use array instead of map. So I figured the time complexity would be O(N lg N). But the solution TLE's.↵
</spoiler>↵
↵
If you see any problems with the code, please let me know as I can't see the problem. If you don't understand a part of the code, please ask and I will clarify.↵
↵
Submission: [submission:255437477]↵
↵
UPD: The runtime takes more than 30 seconds! So I guess the runtime is O(N^2) somehow.
