For yesterday's educational round problem E, I had a pretty funny solution, which I wanted to share.

First, rephrase the problem as counting the number of pairs of such endpoints of paths, instead of the actual paths. Let's count all $$$(u, v)$$$ where $$$u$$$ is an ancestor of $$$v$$$ using a simple DFS, and ignore them now. We will now only focus on calculating pairs where none of them is an ancestor of another (in other words $$$\text{lca}(u, v) \ne u$$$ and $$$\text{lca}(u, v) \ne v$$$). We will calculate for each vertex $$$u$$$ the vertex $$$\text{prv}[u]$$$, which is the deepest vertex $$$v$$$ on the path from the root to $$$i$$$ (different from $$$i$$$ itself) using a dfs. Let $$$\text{gdep}[u]$$$ be $$$\text{dep}[\text{prv}[u]]$$$ (the distance of $$$\text{prv}[u]$$$ from the root). Then, it suffices to find the number of pairs $$$(u, v)$$$ such that $$$c_u = c_v$$$, and $$$\text{dep}[\text{lca}(u, v)] > \max(\text{gdep}[u], \text{gdep}[v])$$$ (since none of $$$c_u$$$, and $$$c_v$$$ must lie again on the path). So we can create buckets by the value of $$$c_i$$$, and inside each bucket, sort the values by $$$\text{gdep}[u]$$$. Processing from right to left, if current vertex is $$$ver$$$ we can do a range subtree add query on the $$$(\text{gdep}[ver] + 1)^{\text{th}}$$$ vertex on path from root to $$$ver$$$ (using euler tour or tree flattening method). Now, count the value of the current vertex $$$ver$$$ using point query operation. This clearly suffices because the vertices processed before this one have stronger conditions on the value of depth of $$$\text{lca}$$$ (because we processed right to left). Also, in every pair there must be some vertex with maximum $$$\text{gdep}$$$, so that vertex will be processed before, and this one after, and this clearly suffices, because there's no overcounting or undercounting. Of course, this is pretty overkill, but I'm sharing it here just for the memes :)

Code: 247980696