CF1651E Sum of Matchings

我们用 $ \mathit{MM}(G) $ 表示图 $ G $ 的最大匹配数。 给定一个二分图。第一部分的顶点编号为 $ 1 $ 到 $ n $，第二部分的顶点编号为 $ n+1 $ 到 $ 2n $。每个顶点的度数都是 $ 2 $。 对于四元组 $ (l, r, L, R) $，其中 $ 1 \le l \le r \le n $ 且 $ n+1 \le L \le R \le 2n $，我们定义 $ G'(l, r, L, R) $ 为包含原图中所有编号在区间 $ [l, r] $ 或 $ [L, R] $ 内的顶点，以及所有两个端点都属于这些区间的边所组成的图。换句话说，从原图中删除所有 $ i \notin [l, r] $ 且 $ i \notin [L, R] $ 的顶点以及所有与这些顶点相连的边，就得到了 $ G'(l, r, L, R) $。 请计算所有满足 $ 1 \le l \le r \le n $ 且 $ n+1 \le L \le R \le 2n $ 的四元组 $ (l, r, L, R) $ 对应的 $ \mathit{MM}(G(l, r, L, R)) $ 之和。

第一行包含一个整数 $ n $（$ 2 \le n \le 1500 $），表示每一部分的顶点数。 接下来 $ 2n $ 行，每行描述图中的一条边。第 $ i $ 行包含两个整数 $ x_i $ 和 $ y_i $（$ 1 \le x_i \le n $，$ n + 1 \le y_i \le 2n $），表示一条边的两个端点。 给定的图中没有重边，并且每个顶点的度数恰好为 $ 2 $。

输出一个整数，表示所有满足 $ 1 \le l \le r \le n $ 且 $ n+1 \le L \le R \le 2n $ 的四元组 $ (l, r, L, R) $ 对应的 $ \mathit{MM}(G(l, r, L, R)) $ 之和。

由 ChatGPT 4.1 翻译