This is kind of off-topic, why are comments insulting other people's families or religions on Codeforces blogs so frequent nowadays? I know there will always be trolls, but recently I feel like the number of such trolls has increased and they hijack almost every blog and start discussing politics, religion etc. For example, this guy's blog / productivity diary where he was sharing what he did during that week (which I think is a really good thing for Codeforces blogs, and on topic) got hijacked by the trolls: https://codeforces.me/blog/entry/127477, and I've seen a few other blogs too, which got hijacked by such trolls, and got deleted. There were some trolls before too, but recently the percentage has increased significantly.

As you can see, I became CM now. But, I registered for the Div. 2 part of Codeforces Round 934 (Div. 1 + Div. 2) before rating update, and in the registration tab for the contest, it doesn't show a * next to my name, which is there in unrated participation (out of competition), and it still shows that my color is blue (even though the rating next to it is 1941). So, will this contest be rated for me, or should I just register for the Div. 1 part of it?

EDIT: It now shows that my color is purple, but it still does not show the * next to my name.

EDIT: For anyone wondering about what happened, I got deregistered from the Div. 2 just before it started, so I guess the system checks whether you're rated for the contest right before it.

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