c_wInf's blog

树上dp

什么是树上dp？字面意思，在树上做dp

但是这个描述不准确，更准确应该是树形dp，树上dp可能只是在树上，有一个dp，不一定是树状转移状态的

状态转移的方向：自顶向下/自底向上

一个自顶向下的例子：树上差分

自顶向下时一个结点的多个子结点会共用一个dp状态栈，所以需要利用回溯的性质

自底向上时一个结点会从多个子结点来转移状态，所以状态转移方程会更复杂；且子结点树可能是\(O(n)\)的，对于关于子结点数\(k\)时间复杂度\(\Omega(k^{1+\epsilon})\)的转移计算方法，菊花树会爆，此时要考虑在子结点上维护一些数据结构或者启发式合并状态或者设计逐结点转移方程

树形dp

例题：没有上司的舞会

例题：树上染色

作业：叶结点划分CF1146F，连通块个数，树上游戏(染色树每个点到所有点路径上颜色数之和)P2664

重心

树的重心(割掉每条边得到重心点权和)P5666

枚举边，边下面考虑重心在重链上单调性，边外面重心位于dfs序中点祖先链上+倍增二分求重心or重心向重儿子移动(边在重子树上则向次重儿子移动)

拎出重心，枚举点，转化为该点子树外多少子树重量介于区间内，dfs序上归并树/集合树状数组or容斥，前缀和求总数-树状数组计算进点和回溯差值

淀粉质

淀粉质模板(边权树上距离为k点对是否存在)P3806

作业：Tree(边权树上距离<=k点对数)P4178，边权树上每个点距离k内点权最大值P6329弱化

直径

捉迷藏P2056(不用淀粉质？)

作业：树上路径(边权树上前k大距离)P12692

\[ \newcommand{\ci}{\mathrm{i}} \newcommand{\e}{\mathrm{e}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\N}{\mathbb{N}} \newcommand{\eps}{\varepsilon} \newcommand{\dsum}{\displaystyle\sum} \]

Abstract

This article develops the exponential and trigonometric functions from first principles using infinite series, avoiding reliance on geometric intuition or pre-existing notions of angle. Motivated by foundational concerns raised in early twentieth-century analysis, the construction is carried out directly on the complex plane. After establishing the algebraic structure and completeness of \(\C\) as a normed vector space, basic results on complex series are proved, including absolute convergence and a Fubini-type theorem. The exponential function is then defined by its power series, shown to be well-defined on \(\C\), and its fundamental properties—such as the exponent law, positivity on \(\R\), and monotonicity—are derived. Trigonometric functions are introduced via the complex exponential, leading naturally to Euler’s formula, addition formulas, and the Pythagorean identity. This approach demonstrates that the classical properties of exponential and trigonometric functions arise purely from analytic and algebraic considerations, without geometric assumptions.

Mainly using BOCF with \(M\), the recursive Mahlo ordinal. For ordinals less than \(\mathrm{BHO} = \psi(\Omega_2)\), normal notation with extended Veblen’s function is also used.

Contents:

1. part 1, to \(\mathrm{SCO}\)
2. part 2, to \(\mathrm{FSO}\)
3. part 3, to \(\mathrm{LVO}\)
4. part 4, to \(\mathrm{BHO}\)
5. part 5, to \(\mathrm{BO}\)

ACMOJ链接

形式化题意

给定长度为 \(n\) 的字母序列 \(S\) ，和长度为 \(m\) 的字母序列 \(T\) ，求 \(S\) 中和 \(T\) 相似的子串有多少个，相似代表离散化后一致，即每一个对应位置字符的序关系保持一致。

原知乎回答

前言

两年前一位姚班大神学长回到高中母校并出了这样一道题：抢红包。

\(10\) 个人抢价值 \(10\) 元的红包，手气最佳同学抢到的红包的期望是多少？

注意这里是最大值，而最大值问题其实要比最小值问题难。当时我硬用积分和一些奇技淫巧给出了最小值的解答—— \(\dfrac{1}{10}\) 。而后大神给出了一个非常漂亮的解答，在这个解答中给出了任意排名的红包期望值。

为了尽量严谨化题意，他给出了一个等价的问题：

一段长为 \(n\) 的环形绳子，随机地切 \(n\) 刀，最长的一段长度的期望是多少？