空想上の人格保持者
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
## 引言 出于种种原因我实现的第一个最大流算法选择了《算法导论》的“前置重贴标签算法”。但如果尝试实现过《算法导论》中最大流算法的话，应该会注意到书中对流网络的定义不支持反平行边（即同时存在 $(u, v), (v, u)$）... 虽然存在对复杂度影响为常数级别的转换为等价图的方法（即把每个结点 $u$ 复制一份…
## 前言 一直没自己实现过最大流，出于偏好写的第一个最大流算法选用了《算法导论》的“前置重贴标签算法”，并且也采用了《算法导论》给出的实现方式。但是《算法导论》中对流网络的定义要求不能有反平行边（即同时存在 $(u, v), (v, u)$）；虽然存在对复杂度影响为常数级别的转换为等价图的方法（把每个结点 $u$ 复…
发现自己做法的后半部分（**Part2**）和 tutorial 不太一样，于是写篇题解记录一下。 ## ~~Part0~~ 首先从一个错误且复杂度爆炸的 dp 引入。 设 dp 的状态记录 $\text{mex}, l, r, k$，每个状态表示的是已经填了一些数字的方案的集合，其中 $\text{mex}$ 表示当…
在讨论《扣 1 复活讨论区》回复：
114514
[](https://www.luogu.com.cn/paste/6bukoj24) [](https://www.luogu.com.cn/training/687043) # P11041 [蓝桥杯 2024 省 Java B] 报数游戏 设 $f(n, d)$ 表示 $[1, n]$ 内可以被 $d$ 整除的数…
在讨论《【更新】洛谷维护公告》回复：
AT RMJ 有生之年（
在讨论《CSP-S T10》回复：
~~（捕捉Mooos）~~ `105` +1 盯着算了好几遍，怎么想都是 `105`（（
在讨论《萌新自闭求题解》回复：
@[ducati](/user/87064) 啊，一对一讲应该还是会比看题解更好懂的... 至少可以先试试（
在讨论《萌新自闭求题解》回复：
@[ducati](/user/87064) 您其实完全可以直接问我的...
在讨论《求问本题结论证明》回复：
瑕疵\*2：和题中限制一样，原树每个结点度数至多为三（
在讨论《求问本题结论证明》回复：
可能的一个瑕疵：注意到当根仅剩下一颗子树时算法会无法继续，因此这里的 “某一时刻” 必须在此之前（在根仅剩下一颗子树之前）
具体来说： 设原树重心度数为三。以重心为根，记 $p_1, p_2, p_3$ 为重心的三个儿子 考虑一种算法，它每次取和上次取的结点不在同一个 $p_1, p_2$ 或 $p_3$ 子树内的最深的结点，将该结点删去（如果是第一次取就没有不同子树的限制） 记初始时 $p_1, p_2, p_3$ 子树的大小为 $a,…
在讨论《怀疑数据有问题》回复：
@[SSerxhs](/user/29826) 原来是这样么 /fad
在讨论《怀疑数据有问题》回复：
fixed 也好快！ ~~虽然貌似只是把可能有问题的数据都直接去掉了qaq~~
在讨论《怀疑数据有问题》回复：
好快 /jk
1. 此题至今无人通过 2. [这份代码](https://www.luogu.com.cn/paste/lseddq6v) 能够通过 POI 给出的数据，以及 bzoj 上的数据，但无法通过此题数据。详见 [自测记录](https://www.luogu.com.cn/record/49138397)、[此题记录](…
在讨论《学术版内容严管规定》回复：
hp
在讨论《如何分别统计树上所有长度的路径的数量》回复：
@[jeffqi](/user/40581) 确实也可以 /fad /kk
在讨论《如何分别统计树上所有长度的路径的数量》回复：
@[jeffqi](/user/40581) 貌似这题用点分也是可以做的 --- 考虑容斥地统计方案。具体来说： 设当前关键点 $r$；设 $r$ 管辖的连通块以 $r$ 为根时的 $r$ 的儿子 $u_i$；设 $u_i$ 子树以 $u_i$ 为根时的各深度的结点数量的多项式 $Q_i(x)$；最后设 $P(x)=\…
在讨论《如何分别统计树上所有长度的路径的数量》回复：
@[糯米w](/user/307202) 啊这，不是（ （大半是统计路径的方式不太一样...） 但您这样做的复杂度是多少；或者更具体地说，在每个关键点处计算的复杂度真的能接受么，当前连通块内每个子树都要做一次 FFT...（如果我没理解错的话；或者要不您更具体地讲下 /kk）
在讨论《如何分别统计树上所有长度的路径的数量》回复：
@[糯米w](/user/307202) 嗯...问题不是在这 我想的点分治，是在关键点处统计经过关键点的路径，并加上下一层连通块的答案（可能描述得比较粗略） 但这两个部分无论哪个都是瓶颈
在讨论《如何分别统计树上所有长度的路径的数量》回复：
@[糯米w](/user/307202) 貌似想假了；括号序估计不太可做（（ 不过您的点分也可以具体讲下么 /kk
在讨论《如何分别统计树上所有长度的路径的数量》回复：
@[jeffqi](/user/40581) （话说同样是两个 $\log$ 貌似还有一种做法...可以转成括号序然后 线段树+FFT 搞，这样常数会小点）
在讨论《如何分别统计树上所有长度的路径的数量》回复：
@[jeffqi](/user/40581) /fad 不过这样就是 $\Theta(n\log^2 n)$ 了... 不知道有没有其它做法能更快....
在讨论《如何分别统计树上所有长度的路径的数量》回复：
@[jeffqi](/user/40581) （草也可能您指的 “点分” 就是 “边分”）
在讨论《如何分别统计树上所有长度的路径的数量》回复：
@[jeffqi](/user/40581) 能具体讲下么qwq （边分+FFT 我倒是有想到...）
在讨论《如何分别统计树上所有长度的路径的数量》回复：
@[jeffqi](/user/40581) 无边权 这里 “路径长度” 指路径包含的点的数量（补充）
在讨论《「TOCO Round 1」新春欢乐赛 赛时答疑帖》回复：
hp
在讨论《题解的连边方法如何保证每个部分恰有一个关键点？》回复：
@[yyyg_2019](/user/143577) (=・ω・=)