Attachments

• Contest Rules

Overall Schedule

• To contestants: Please wear the blue hoodie on 19th, 21st and 23rd Feb, and the white one on 20th and 22nd Feb.
• To staff and volunteers: Please wear the red hoodie on 19th, 21st and 23rd Feb, and the green one on 20th and 22nd Feb.

Notice

1. On February 19th, there is no group dining. You may order room service and we will cover the cost.
2. For everyday’s breakfast, please use your room card to enter the dining room.
3. For all transportation from Sanyapo Campus, please be at Hotel Lobby, The Amber House Songshan Lake Dongguan in time.
4. If you encounter any unexpected circumstances, please contact volunteers immediately.
5. To ensure the safety of all participants and the smooth operation of the event, please strictly adhere to the on-site safety regulations.
   • During the event, do not leave the designated area without permission, and refrain from climbing, chasing, using open flames, or engaging in any other behavior that may endanger yourself or others.
   • All participants must follow the instructions of staff and volunteers, as well as comply with venue signage and safety notices.
   • If any personal actions (such as ignoring warnings, unauthorized movement, or dangerous activities) result in personal injury, property damage, or other adverse consequences, the individual involved shall bear full responsibility for all resulting liabilities and losses.
   • The event organizers will not be held accountable.

Programming Environment

• OS: Ubuntu 24.04.1 LTS
• Desktop: GNOME Flashback
• Editors: vi/vim, gvim, emacs, gedit, geany, kate
• IDEs: Eclipse, IntelliJ, CLion, PyCharm, RustRover, Code::Blocks, Visual Studio Code
• Contest Control System: DOMJudge 8.3.1

Languages

Conference Information

Linear Systems Surprises

Presenter: __Richard Peng__

Abstract: Algorithms researchers strive to design better ways of solving problems that are central to many disciplines. Systems of linear equations arise throughout engineering and sciences in tasks ranging from physical simulation to data analytics. In many cases where linear systems don’t exactly model the problem, they provide the steps that lead to the solutions. Despite linear systems’ storied history spanning centuries, the current best algorithms for general linear systems, as well as many important subclasses, remain comparatively slow.

Over the last few decades, algorithms researchers developed entirely new approaches to solving linear systems. These progress led to accelerations in many applications, as well as entirely new theoretical frameworks for designing and analyzing algorithms. This talk will briefly overview some of the surprising ways of thinking about approximations, iterative convergences, and algebraic structures that originated from studying linear systems.

An Introduction to Symbolic Program Generation

Presenter: __Ruyi Ji__

Abstract: Large Language Models (LLMs) have recently achieved remarkable success in program generation, particularly in competitive programming. For example, OpenAI reported that its o1 model achieved gold medal-level performance in last year's International Olympiad in Informatics (IOI), and its o3 model attained an estimated rating of ~2700 on Codeforces, ranking among top competitive programmers.

Despite these impressive milestones, current LLMs still suffer from several limitations. One major challenge is their inability to deduce general rules purely from examples, as their inference heavily depends on the presence of natural language. To address this limitation, symbolic approaches — representing a different paradigm of artificial intelligence — offer a complementary solution. Unlike LLMs, which rely on fitting vast amounts of data through large neural networks, symbolic systems represent knowledge via a small set of interpretable rules and perform reasoning by searching through combinations of these rules. While such systems are less effective at handling natural language, they excel at reasoning directly from structured examples.

In this presentation, I will provide an overview of symbolic program generation (i.e., program synthesis) and share recent progress in synthesizing efficient programs and complex algorithms.

Tight Bounds for Retrieval Data Structures By

Presenter: __Tingqiang Xu__

Abstract: Retrieval data structures are data structures that answer key-value queries without paying the space overhead of explicitly storing keys. The problem can be formulated in four settings (static, value-dynamic, incremental, or dynamic), each of which offers different levels of dynamism to the user. In this presentation, I will talk about optimal bounds for the final two settings (incremental and dynamic) in the case of a polynomial universe. This complete a line of work that has spanned more than two decades, and also come with a surprise: the incremental setting, which has long been viewed as essentially equivalent to the dynamic one, actually has a phase transition, in which, as the value size v approaches log n, the optimal space redundancy actually begins to shrink, going from roughly n log log n (which has long been thought to be optimal) all the way down to Θ(n) (which is the optimal bound even for the seemingly much-easier value-dynamic setting).

Practice on medical LLMs

Presenter: __Benyou Wang__

Abstract: Recently, OpenAI's ChatGPT and various open-source community models, such as LLaMA 3, have significantly advanced the development of AI applications. In the medical field, both proprietary and open-source models hold great potential. However, when it comes to solving real-world medical problems, there is still a "last mile" to cover. In this Speech, we will introduce our team's development of the medical large language model, HuatuoGPT, and its multilingual and multimodal extensions, the Apollo series. We will also discuss the technical solutions for HuatuoGPT-o1, which aim to enhance the performance and interpretability of large language models, particularly in the context of longer diagnostic reasoning chains. Finally, we will look ahead to the future development of medical LLMs. Specifically, we will explore the potential of using AIGC technology to create a large number of patient agents to train both human and AI doctors. By doing so, we can accumulate real patient needs and doctor feedback, ultimately working towards the development of generalist medical artificial intelligence (GMAI).

Universal Cup 是一个致力于服务竞赛编程社区的组织，专注于提供高质量的训练资源并举办全球线下赛事。2025 年 Universal Cup 总决赛（即第二届 Universal Cup 总决赛）是本赛事第二赛季的最终比赛。

共有 20 支队伍通过在线比赛、半决赛或线下夏季峰会晋级，将争夺第二届 Universal Cup 冠军的头衔。

竞赛形式

1. 竞赛时长为五小时。在不可预见的情况下，科学委员会主席有权修改竞赛时长。如竞赛形式或时长发生变更，参赛队伍将以统一方式及时获悉。
2. 竞赛题目数量不少于 10 题，且不超过 14 题。
3. 队伍可通过 Clarification Request 提交对题目可能存在错误的申诉。澄清请求必须仅使用英文撰写。
4. 竞赛期间可能发布 Clarification，内容可能包括题目说明、附加细节、额外示例或对题目的修改（包括补充、删除或更改）。
5. 所有 Clarification 信息均仅以英文提供，并会在竞赛现场统一公布。

题目

1. 所有题目陈述仅提供英文版本。
2. 参赛队伍可使用字典或在线翻译工具自行翻译题目内容，官方不提供翻译。
3. 任何题目均不会提供部分分数。
4. 竞赛题目类型包括：

• 标准输入/输出题：程序需从 标准输入 读取数据，并将结果输出到 标准输出。
• 交互题：程序需通过标准输入/输出与 交互器 进行交互。
• 多次运行题：程序将多次运行，每次使用不同的输入数据。
• 仅输出题：参赛队伍无需提交程序，仅提交最终答案。

提交与评测

1. 竞赛评测平台采用 DOMjudge，一个开源自动化竞赛系统。
2. 支持的编程语言包括 C、C++、D、Python 3、Java、Kotlin 和 Rust。
3. 详细的语言版本与规格请参考 TechNote 文档。
4. 每次提交的评测结果仅为通过（Accepted）或未通过（Rejected），不会提供部分分数或错误测试点编号。
5. 未通过的提交将标记为以下之一：

- 编译错误（CE）
- 运行时错误（RTE）
- 时间超限（TLE）
- 结果错误（WA）
- 无输出（NO）
- 输出超限（OLE）

计分、排名与奖项

1. 队伍按照解题数量进行排名，解出相同题目数量的队伍按照 罚时 进行排名。
2. 如罚时相同，则按 最后一个通过题目的提交时间 进行排名。如果仍有相同，将按照以下方式，直到决出所有相同队伍的名次：
   • 所有排名相同的队伍将按照他们的 最后一次通过提交的提交时间（精确到毫秒） 排名。该时间越早的队伍排名越高。没有通过任何题目的队伍的时间被视为 00:00:00.000
   • 如果仍有相同，这些排名相同的队伍将会按照他们在第 2 届 Universal Cup 中的 rating 进行排名。
   • 如果仍有相同，一道用于打破平局的额外题目将决定这些排名相同的队伍的排名。
   • 如果仍有相同，将通过抽签决定这些队伍的排名。
3. 罚时 计算方式为 所有解出的题目的耗时总和 加上 该题目的额外罚时。
4. 题目的耗时是指从竞赛开始到首次通过该题的提交时间，以分钟计算。
5. 题目的额外罚时为 20 分钟 乘以 首次通过前所有未通过的提交次数（编译错误除外）。
6. 未解决的题目不计算罚时。
7. 比赛进行 4 小时后，实时排名将被冻结，之后的提交结果将在榜单上显示为“待定”。
8. 金牌将会颁发给比赛中获得前三名的队伍（共三名）。
9. 银牌将会颁发给比赛中获得第四名至第七名的队伍（共四名）。
10. 铜牌将会颁发给比赛中获得前八名至第十二名的队伍（共五名）。
11. 科学委员会主席有权决定为队伍颁发额外的奖牌。

竞赛环境

1. 每支队伍仅配备 一台计算机。
2. 所有队伍的计算机配置相同。
3. 队伍可自带 鼠标、键盘 或 手写板 进入比赛区域，但不保证所有外接设备都能正常使用。
4. 队伍不得携带 个人计算机、手机、计算器 或其他电子设备进入比赛区域。
5. 技术委员会有权检查队伍携带的外接设备。如有争议，技术委员会主席的决定为最终裁决。
6. 参赛队伍可浏览互联网以获取任何资料。
7. 竞赛期间，禁止与队伍以外的任何人交流。
8. 任何在互联网上分发题解、代码或辅助程序的行为均被严禁。
9. 参赛队伍不得提交恶意代码，包括但不限于攻击评测系统或恶意占用评测资源。
10. 在科学委员会主席指示前，不得触碰比赛工作站的任何设备。

申诉

1. 参赛队伍可对题目内容、提交评测结果或竞赛相关决定提出申诉。
2. 申诉内容必须仅使用英文撰写。
3. 评测裁判将对申诉做出决定，可能会调整竞赛期间的评测结果。
4. 如果对裁判决定仍有异议，可向 Universal Cup 科学委员会主席提交最终申诉。
5. 科学委员会主席的决定为最终裁决。

竞赛委员会

科学委员会

• 主席： Qingyu
• 副主席： jiangly
• 委员： bulijiojiodibuliduo, quailty, Heltion, Lynkcat

技术委员会

• 主席： Qingyu
• 委员： cubercsl, dup4, Tangent

组织委员会

• 主席： chenjb

The Universal Cup is an organization aiming at serving the competitive programming community, dedicated to provide high quality training resources and host onsite global events. The 2025 Universal Cup Final Contest (or The 2nd Universal Cup Finals) is the final contest of the 2nd season of our event.

A total of 20 teams have qualified through online competitions, semifinals, or onsite summer summits to compete for the title of The 2nd Universal Cup Champion.

Contest Format

1. The competition will last five hours. The Chair of the Scientific Committee has the authority to modify the contest duration in the event of unforeseen circumstances. If any changes occur regarding the contest format or duration, participants will be notified in a timely and uniform manner.
2. There will be at least ten (10), but no more than fourteen (14) problems in the contest.
3. Teams may submit claims regarding potential mistakes in a problem via a clarification request. Clarification requests must be written in English only.
4. Clarifications may be issued during the competition. These clarifications may include explanations of problem statements, additional details, extra examples, or modifications to a problem (including additions, removals, or changes).
5. All clarifications will be provided in English only, and notifications will be announced at the competition venue.

Problems

1. All problem statements will be provided in English only.
2. Teams may use dictionaries or online translation tools to translate the statements into other languages. No official translations will be provided.
3. No partial scores will be awarded for any problem.
4. The types of problems in the competition include:
   • Standard I/O problem: Your program must read input from the standard input and write output to the standard output.
   • Interactive problem: The program interacts with an interactor through standard I/O.
   • Multiple-Run Problem: The program will be executed multiple times, each with a different input.
   • Output-Only Problem: Teams do not submit a program but instead submit the final answers directly.

Submissions

1. The judging platform of the competition is DOMjudge, an open-source automated system to run programming contests.
2. The supported programming languages include C, C++, D, Python 3, Java, Kotlin, and Rust.
3. The detailed language specifications should be referred to in the TechNote document.
4. Each submission is judged as accepted or rejected. No partial scores or failed test ID will be given to the teams.
5. Rejected runs will be marked with one of the following:
   • Compilation Error (CE)
   • Runtime Error (RTE)
   • Time Limit Exceeded (TLE)
   • Wrong Answer (WA)
   • No Output (NO)
   • Output Limit Exceeded (OLE)

Scoring, Ranking, and Awarding

1. Teams are ranked according to the most problems solved.
2. Teams who solve the same number of problems are ranked first by the least penalty, with the following tie-breakers in order:
   • the tied teams will be ranked according to their last AC time, in milliseconds. Teams has the earlier last AC time will be ranked higher. Teams did not solve any problems will have the last AC time as 00:00:00.000.
   • if there is still a tie, the tied teams will be ranked according to their ratings on The 2nd Universal Cup.
   • if there is still a tie, the tied teams will be ranked according to an additional play-off task.
   • if there is still a tie, a lucky draw will determine the ranking of all tied teams.
3. The penalty is the sum of the time consumed for each problem solved plus the penalty in that problem.
4. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submission of the first accepted submission, in minutes.
5. The penalty in a problem is twenty (20) minutes times the number of non-accepted submissions before the first accepted submission, excluding the ones with a compilation error verdict.
6. There is no time consumed for a problem that is not solved.
7. The leaderboard will be frozen 4 hours after the contest starts, and the results submitted after 4 hours will be shown as pending on the leaderboard.
8. Gold Medals will be awarded to the Top 3 teams (1st, 2nd, and 3rd places).
9. Silver Medals will be awarded to the Next 4 teams (4th to 7th places).
10. Bronze Medals will be awarded to the Next 5 teams (8th to 12th places).
11. Additional Medals might be awarded at the decision of Chair of the Scientific Committee.

Contest Environment

1. Each team will be provided with one computer only.
2. All teams will have equivalent computing equipment.
3. Teams may bring their own mouse, keyboard, or graphics tablet to the contest area. However, it is not guaranteed that all the external devices could work properly on your workstation.
4. Teams may not bring their own computers, smartphones, calculators, or other electronic devices to the contest area.
5. The Technical Committee may inspect the external devices brought by a team before the contest. In case of ambiguity, the decision of the Chair of the Technical Committee shall be final.
6. Teams are allowed to browse the Internet to access any materials.
7. Teams are prohibited from communicating with anyone outside their team during the contest.
8. The distribution of any problem-solving materials, including ideas, codes, or auxiliary programs, on the Internet is strictly forbidden.
9. Teams may not submit malicious codes, including but not limited to attacks on the judging platform and malicious occupation of evaluation system resources.
10. Do not touch anything at the team workstations until so directed by the Chair of the Scientific Committee.

Appeal

1. Teams may submit an appeal regarding potential mistakes in any problems, verdicts of the submissions, or other contest decisions.
2. Appeals must be written in English only.
3. Judges will give a decision to an appeal, which might change a verdict given during the contest.
4. If you are still not satisfied with the results given by the judges, you may file a final appeal with the Universal Cup Scientific Committee.
5. The decision of the Chair of the Scientific Committee shall be final.

Competition Staff

Scientific Committee:

• Chair: Qingyu
• Deputy Chair: jiangly
• Members: bulijiojiodibuliduo, quailty, Heltion, Lynkcat

Technical Committee:

• Chair: Qingyu
• Members: cubercsl, dup4, Tangent

Organizing Committee:

• Chair: chenjb

A. 铁甲战士

除了最开始，抽牌堆里至少包含一张牌，也就是刚打出的那张。下面默认抽牌堆里已经包含一张牌。可以发现，如果在出剑柄打击后不出耸肩无视，那么后面迟早会把手牌全部出完，无法持久地打下去，所以剑柄打击后必须出耸肩无视。同理，如果出了一张狂怒/全身撞击，那么下一张必须要打剑柄打击。因此除了游戏开头，一定是狂怒/全身撞击，剑柄打击，耸肩无视循环出。对于游戏开头和结尾只有 $O(1)$ 种可能，可以直接枚举。可以发现，一定是一个前缀打狂怒，一个后缀打剑柄打击，直接二分分界点即可。需要写高精度。

B. 小青鱼

如果每次操作是操作一整行/列/对角线，那么题目等价于 3sum 问题，可以用一次 FFT 解决。

那么现在区间怎么做。考虑分块。把 $n\times n$ 分成 $n/B\times n/B$ 个 $B\times B$ 的块。这样每一条线会经过 $O(n/B)$ 个整块和 $O(B)$ 个散点。整块同样 FFT。散点暴力加入。复杂度 $O(n\sqrt{n\log n})$。

不想要这个 $\log n$ 因子。可以发现行的多项式的点值可以在横着扫时保留。每次更新一个单点系数可以 $O(B)$ 改完点值。对列和斜同理。这样 $\log n$ 就没了。复杂度 $O(n\sqrt n)$。

C. 货币

相当于对每个 $i$，我们需要在 $(1,i)$ 到 $(1,i+1)$ 与 $(2,i)$ 到 $(2,i+1)$ 之间选择一个走。选每一种需要一个代价，如果 $i$ 和 $i+1$ 选择了不同的行，那么就需要额外付出 $(1,i+1)$ 到 $(2,i+1)$ 之间边的代价。再加上 $m$ 条限制，是一个小型的切糕模型，直接建图跑网络流即可。

D. 广为人知题 2

本题为 IDM Problem 的 CountDistinct 查询。详细做法见 Nearly Optimal Internal Dictionary Matching。

给所有串赋一个权值 $v_t$，其中 $t$ 为一个 $s$ 的子串，初始均为 $0$。我们直接将所有模式串对应的 $v_t$ 加 $1$，查询的答案即为查询串 $s[l,r]$ 所有本质不同子串中 $v$ 的和。

考虑所有串形成的 trie（这里 trie 字符着加，为了匹配正串 SAM）。记 $f_u$ 为 $u$ 到根的所有串的 $v$ 之和。答案为 trie 上所有是 $s[l,r]$ 子串的点的 $v$ 之和。显然构成一个 trie 上包含根的连通块，答案即为：

$$\sum\limits_{u是叶子}f_u-\sum\limits_u (u儿子个数-1)f_u$$

首先考虑后者。按 $r$ 扫描线，考虑 LCT，维护 SAM 上连续上一次出现位置相同的节点。每次 access 时遇到一个连续段时，考虑段尾的点何时儿子个数 +1，应为 $l\leq \mathrm{last}-\mathrm{len}$ 且 $s[1,r]$ 所在子树第一次出现节点（即上一个连续段中的 $\mathrm{last}$ 不会在这里贡献）。所以对 $l$ 是一个区间加。查询即为单点查询。该部分时间复杂度 $O(n\log^2n+q\log n)$。

再考虑前者。首先叶子一定左端点为 $l$。其次若 $s[l,t]$ 非叶子，说明存在 $s[l',r']=s[l,t]$ 且 $t

最后考虑如何求出 $\sum\limits_{i=x}^r f_{s[l,i]}$。差分后变为若干个 $\sum\limits_{i=l}^r f_{s[l,i]}$。而这等价于广为人知题查询（IDM Problem 的 Count 查询），可以用基本子串结构（见 Nearly Optimal Internal Dictionary Matching）在 $O((n+q)\log n)$ 内解决。

总时间复杂度为 $O(n\log^2 n+q\log n)$。若 $n,q$ 同阶，可优化至 $O\left(\frac{n\log^2n}{\log\log n}\right)$。

E. 浅斟低唱

考虑维护长度 $\geq 2$ 的所有 0 的连续段和 1 的连续段，每次 1 操作是让所有 0 连续段左移一位，所有 1 连续段右移一位，2 操作同理。

例子：经过 1 操作后，

01010000111101010001110111100010101 变成

10100001011110100010111011100101010

唯一出现问题的可能即为存在一个 0 连续段与一个 1 连续段撞上了。此时可以暴力修改，由于所有连续段长度总和这时会减 2，且长度总和初始最多为 $n$，修改最多增加在每次操作的边界 ，所以总暴力修改次数为线性。

总时间复杂度为 $O((n+q)\log n)$。

F. Trash Problem

枚举左边界。此时从左往右扫，记录每个格子当前是一个 $2\times 2$ 的一半还是已经完成。每次扫的时候如果当前是一半但是下一个是黑格，那么包含这一行的就全不合法。否则如果当前是白格，就将这个状态异或 $1$。扫到某个时刻，一个区间合法当且仅当当前这些状态都是已完成，且这个区间不包含前面所说的那些行，且与所有出现过的连续状态 $1$ 的区间交的长度为偶数。前两个条件容易满足，重点在于第三个条件。

可以发现，$[l,r]$ 与所有连续状态 $1$ 的区间交的长度为偶数等价于 $[1,r]$ 与所有连续状态 $1$ 的区间交的长度为奇数的区间左端点集合等于 $[1,l-1]$ 与所有连续状态为 $1$ 的区间交的长度为奇数的区间左端点集合相同。直接扫描线扫 $r$，哈希一下，如果哈希表 $O(1)$ 复杂度即为 $O(n^3)$。

G. 分析

注意到代价为 $A$ 的操作可以直接视为加了一条重边，所以我们可以先执行所有代价为 $A$ 的操作，在考虑怎么走。可以发现加完边之后需要执行的 $B$ 操作次数即为度数为奇数的点数除以 $2$ 再 $-1$（如果没有度数为奇数的点即为 $0$）。

树形 dp，过程中考虑是否加重边，状态内记子树根的度数奇偶性和是否有度数为奇数的点即可。

时间复杂度 $O(n)$。

H. 代数

题解

首先把子树大小的 $k$ 次方改为选 $k$ 个点都在子树内的方案数。进一步，可以看作有 $n+1,n+2,\dots,n+k$ 这 $k$ 个点，每个点随机选择 $1,2,\dots,n$ 中的一个点作为父亲，问有多少种方案使得它们都在 $u$ 子树内。

考虑从前往后 dp，设 $d[i][j]$ 表示前面 $i$ 个点考虑完，有 $j$ 个点还存在没出现的儿子的子树里有 $n+1,\dots,n+k$ 这 $k$ 个点之一。那么转移即为：

1. 新出现的点子树里没有 $n+1,\dots,n+k$ 这 $k$ 个点之一。那么随便接到任意一个点上即可。
2. 新出现的点子树里有这 $k$ 个点之一，假设接到了点 $u$ 下面，此时 $u$ 还有别的没出现的儿子的子树里有这 $k$ 个点之一。
3. 新出现的点子树里有这 $k$ 个点之一，假设接到了点 $u$ 下面，使得 $u$ 没有没出现的儿子的子树里有这 $k$ 个点之一。

要计算每个点的答案，需要从前往后做一遍，转置之后从后往前再做一遍，最后在中间统计答案即可。

时间复杂度 $O(nk)$。

I. 二十二

首先忽略所有没有用的操作。其次，全局取 min 操作一定是从小到大操作的，因为如果有两个前面大右边小，前面的一定没用，可以把它放到紧挨着小的的右边，也没用。这样每一个 max 操作就可以放在任何一个 min 操作前面，可以看作对（这个 min 对应的 $c$ 或者原本的 $c$）取 max。

所以结论即为把所有区间 max 操作的 $c$ 变为所有比 $c$ 小的 min 操作的值之一或者不变后，先操作最小的全局 min，后操作所有 max 操作，有多少种最终序列。可以区间 dp，dp 数组类似 $dp(l,r,x)$，表示区间 $[l,r]$ 内最终序列的所有数均 $\geq x$ 且 $l-1,r+1$ 两个位置 $< x$ 的方案数。因为这样只需考虑被 $[l,r]$ 包含的 max 操作。每次枚举区间最小值转移即可，会有亿点细节。

在 $n,m,k$ 同阶时，时间复杂度为 $O(n^4)$。

J. 我以渺小爱你

条件等价于把每条 hyperedge $(x,y,z)$ 拆成三条边 $(x,y),(y,z),(z,x)$ 后建成的无向图中不包含四元环。

首先构造图 $\mathrm{ER}_q$：

点：$\bmod q$ 意义下三维空间的所有不同直线。

边：两条直线垂直。

容易证明 $\mathrm{ER}_q$ 有点数 $q^2+q+1$，边数 $\frac 12 q(q+1)^2$，且图中不存在四元环。

构造答案：hyperedge 为 $\mathrm{ER}_q$ 中所有的三角形。容易验证满足边数条件。

K. 应氏杯

在钦定一个点是极小值之后，它和周围点之间的大小关系就确定了。

一个经典结论：对于一个森林，如果所有父亲小于儿子，那么赋一个排列的方案数为 $n! \prod_u \frac 1{siz_u}$。

考虑树形 dp，记 $d[u][i][j]$ 为 $u$ 子树内，钦定了 $i$ 个点为极小值，当前小于关系构成的子树大小为 $j$ 的方案数。每次钦定一个点为极小值时，它小于所有儿子，且小于它的父亲。小于它的父亲可以通过容斥变为无限制减去父亲小于它。

是一个二维背包。把一维改成维护点值+插值之后，可以做到 $O(n^3)$。

In the previous two rounds of decisions, we received 45 problems from 22 problem authors. Problem authors who submitted problems can check their review status at https://qoj.ac/proposals.

The Universal Cup Finals is still accepting problem proposals! We will provide CN¥2,500 (or US$300) for each accepted problem. Even if the problem is not selected, there is a chance to receive a small gift from the committee! Problems of any difficulty and style are welcome! Interested users are welcome to contact [email protected] to submit problems. The deadline of submitting tasks is Feb 7, 2025.