Yes, the worst-case time complexity of my code is also O(N^3), yet it still gets accepted.

377380034

For Problem E, I have an approach: iterate every node in the tree and set it as the root in turn. Let the current root be u, which has cnt subtrees. We store the node count corresponding to all possible path lengths obtainable from each subtree into a two-dimensional array with the syntax: g[cnt].push_back(length_node).

We then split the problem of selecting three nodes into two scenarios: ① Node u must be chosen. The remaining two nodes are selected from two different subtrees of u. ② Node u is excluded entirely; all three nodes are picked from three distinct subtrees of u.

For Case ①: the problem reduces to: given cnt arrays whose total element count sums to n, count the number of valid ways to pick two distinct arrays, then pick one value from each such that the sum of the two values equals d−1.

For Case ②: the problem becomes: given cnt arrays whose total element count sums to n, count the number of valid ways to pick three distinct arrays, then pick one value from each such that the sum of the three values equals d−1.

The total count of valid configurations rooted at u is the sum of results from the two cases above.

I can solve Case ① in O(N) time, but Case ② runs in O(N^2). Since we need to process all N nodes as roots, the worst-case overall complexity should theoretically be O(N^3).

Yet the code still passes all test cases, and I am confused why this happens.

I couldn't open your submission, but I followed your method and changed my own gcd function to the inbuild std::gcd. However, it still TLE just like before. Why is that?

Why did I get TLE when following the solution approach for Problem C2???