树形背包好题，推式子感觉十分自然，刚好用 $\LaTeX$ 推的式子顺便写一下题解。 ## Statement 给定一颗 $n$ 个节点的无向树，要求选取 $k$ 个特殊点，与这些特殊点相连的点（除自身外）被覆盖，求把 $n$ 个点全部覆盖的总方案数，答案对 $10^9 + 7$ 取模（$1 \le n \le 10^…

同步发表于 [Thy's Blog](https://bronzemelontnt.github.io/post/13808/)。 # 二叉搜索树 ## Definition 二叉搜索树（$\text{Binary Search Tree}$）是一种形状如二叉树的数据结构，用于**快速查找**和**增加删除**操作，它…

题目链接：[Problem - 1823F - Codeforces](https://codeforces.com/problemset/problem/1823/F) ## Statement 给定一棵 $n$ 个节点的树，求从节点 $S$ 到 $T$ 过程中经过每个点次数的期望值，答案对 $998244353$…

在掌握了多项式的加法和乘法，并且通过 FFT 和 NTT 将时间复杂度降到了可以接受的 $\mathcal{O}(n \log n)$，我们就可以完成许多代数可以完成的基本运算了。 ## 多项式乘法 [P3803 【模板】多项式乘法（FFT） - 洛谷](https://www.luogu.com.cn/problem…

## 前言 这一节用于讲解拉格朗日插值法（Lagrange Polynomial）和快速傅里叶变换（Fast Fourier Transform），但是含有前置知识，因此有大量学过的知识可以直接跳过，存在大量证明会放出相应的链接。 ## 多项式 ### 基本概念 我们将形如 $\textstyle{\sum a_nx^…

在讨论《JRKSJ 的比赛 Extra Round 作弊名单》回复：

读懂 AI 的思路自己写代码是不是就根本封不掉了

在讨论《建议撤下题解》回复：

zc，我测的本地 3s+，建议同时添加 Hack。@[Maxmilite](luogu://user/274993) @[Alex_Wei](luogu://user/123294)

[如果你稳定错在第 2448 行](https://codeforces.com/problemset/submission/487/304641886)，那么恭喜你来对地方了。 在询问为单点修改时，将代码中的： ```cpp scanf("%s%d%d", &opt, &x, &y); ..... SGT.modif…

在讨论《请求更换题面》回复：

@[Maxmilite](luogu://user/274993) @[离散小波变换°](luogu://user/68344)

将分配内存的函数开成两倍： ```cpp inline int* allocate(size_t size) { int *res = topf; return topf += size << 1, res; } ``` 具体原因可以看这个[帖子](https://www.luogu.com/discuss/20579…

在讨论《进食后人》回复：

%%% 不仅过了样例还拿了 24pts。

二分临界值的代码 ```cpp bool check(int mid) { __int128 sum = 0; for (int i = 1; i (__int128)M) return false; } return sum <= (__int128)M; } ``` 这是因为循环中的 $k$ 可达到 $10^{18…

开大空间，包括手写栈等等。 开 long long 并且将 INF 开大。

在讨论《MnZn 刚学指针1μs，代码厌氧求条》回复：

原因是因为 O2 优化会提前返回改变前的 x 和 y。 此贴结。

在讨论《MnZn 刚学指针1μs，代码厌氧求条》回复：

刚刚把代码复制问了 ChatGPT，它改了一改直接过了。 源代码中的 merge 函数： ```cpp Node* merge(Node *x, Node *y) { if (!x || !y) return x ? x : y; if (x -> pri >= y -> pri) x = clone(x), x ->…

在讨论《MnZn 刚学指针1μs，代码厌氧求条》回复：

刚刚把代码复制问了 ChatGPT，它改了一改直接过了。 源代码中的 `merge` 函数： ```cpp Node* merge(Node *x, Node *y) { if (!x || !y) return x ? x : y; if (x -> pri >= y -> pri) x = clone(x), x…

这份代码已经过了（[link](https://www.luogu.com.cn/record/198655190)），但是相同的一份加上 O2 就会全部 RE（[link](https://www.luogu.com.cn/record/198655431)），包括本地测得的小样例。关了 O2 卡了很久常才过的。 请…

这是我之前写的[指针版本](https://www.luogu.com.cn/record/198607194)，最后两个点 MLE 了，改成[数组](https://www.luogu.com.cn/record/198609444)就直接过了。。。

问题应该很好找，这三个测试点不存在寻找不到前驱后继的情况。 如果出现了莫名其妙的 MLE 的情况，树套数的做法不至于卡空间，相反尝试开大空间，

[https://www.luogu.com.cn/problem/P3567](https://www.luogu.com.cn/problem/P3567)。 应该是这道题的加强版，$N$ 扩大了十倍。

在讨论《AI 题目翻译测试》回复：

而且 [P7062](https://www.luogu.com.cn/problem/P7062) 里面把题目陈述的代码块给翻译了。。。

在讨论《AI 题目翻译测试》回复：

建议直接像 Vjudge 一样原文和翻译分栏显示。

手写队列记得开大一些，一次 $\text{SPFA}$ 的进队次数实际上多余总的点数（本人因为数组爆了输出了负数以为是别的问题调了一个多小时）

[像这样](https://www.luogu.com.cn/record/196859543)，原因在于这道题的最大子段和选取的子段不能为空，注意好在插入时和覆盖时树中的 `maxsub` 信息。 并且如果你使用的是 FHQ Treap 在 `pushup` 时子树不一定都有，空的子树继承上来的信息很有可能导致 `m…

在文章《dsu on tree全家桶》发表评论：

%%%%%%%%%%%%%%%

在文章《题解：CF2040C Ordered Permutations》发表评论：

应该是从大到小放入每个数吧

在讨论《dinic求条》回复：

没有用弧优化

## Pre 怎么都说 T1 好想但难调啊，简单贪心 + 小模拟评蓝还是太高了，这里就给出一种好写又好调的并查集做法。 ## Solution 根据题意可知，$t_{k, i} = 1(k \in \{ 1, 2\}, 1 \le i \le n)$ 的连续的 $i$ 所代表的 $s_{k, i}$ 之间可以任意互换，…

在讨论《WA两个点求调》回复：

感觉做法假了，其他人都多开了一维。

在讨论《WA两个点求调》回复：

link：https://atcoder.jp/contests/joi2020ho/submissions/60023475