QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: Diaosi

Posted at: 2026-09-13 22:42:08

Last updated: 2026-09-13 22:43:46

Back to Problem

Editorial for Problem #18200

First build a graph $G=(V,E)$ on the $2n$ accounts. An edge $(u,v)\in E$ means that $u$ and $v$ can still belong to the same player. Initially $G$ is complete. When the account $x$ at rank $k$ plays, $x$ cannot be paired with any account currently below it, so we delete all such edges. Then we swap ranks $k$ and $k-1$.

The key observation is the following invariant.

For any $a < b < c$, if $(a,b),(a,c),(b,c)\in E$, then in the current ranking, $a$ must be above both $b$ and $c$. Otherwise, when one of these accounts crosses another one, at least one edge of the triangle would be deleted.

Hence we get two closure properties: $$ (a,b),(b,c)\in E \Rightarrow (a,c)\in E, $$ and $$ (a,c),(b,c)\in E \Rightarrow (a,b)\in E. $$ Indeed, if a required edge is missing, consider the first event that deleted it. Just before that event, the three edges formed a triangle, contradicting the invariant.

Now define $$ \text{parent}(v)=\max\{u < v\mid (u,v)\in E\}, $$ if such $u$ exists. These parent edges form a rooted forest. The two closure properties imply the following: for any $u < v$, $(u,v)\in E$ iff $u$ is an ancestor of $v$ in this forest. If $u$ is an ancestor of $v$, then repeated use of the first closure along the ancestor chain gives $(u,v)\in E$. Conversely, if $u < v$ and $(u,v)\in E$, then by the definition of $\text{parent}(v)$, we also have $(\text{parent}(v),v)\in E$. The second closure implies $(u,\text{parent}(v))\in E$, so by induction $u$ is an ancestor of $\text{parent}(v)$, hence also an ancestor of $v$.

Therefore, every vertex can be matched with any vertex in its subtree, and there are no edges between different child subtrees or different trees.

Thus we only need a tree DP. Let $f_{u,k}$ be the number of ways inside the subtree of $u$ such that exactly $k$ vertices remain unmatched. Merge the children by standard tree knapsack, then decide whether $u$ remains unmatched or is matched with one unmatched descendant.

So the final answer is $\prod_{\text{parent}(u)=\varnothing} f_{u,0}.$ The total complexity is $O(n(n+m))$.

Comments

No comments yet.