题目大意：
初始时有一棵4个节点的三叉树
每次操作在一个叶子节点下面加入两个节点
问每次操作完树的直径

设当前树的直径为S-T
每次加入节点后，树的直径至多只会改变一个端点，另一个节点仍是S 或T

证明如下

• 考虑加入节点x 的父节点$x_{fa}$，在x 未加入时，根据直径的求法，离$x_{fa}$最远的点一定是S 或T
• 再加入x 后，易得离$x_{fa}$最远的点还是S 或T，因此离x 最远的点也是S 或T

因此每次求一遍x 到S，T 的距离，若大于S-T 就更新

代码就不放了

题目大意：
给出一棵黑白两色的树
每次操作可以改变一个同色联通块的颜色
问最少需要几次操作

首先缩个点，显然每次操作改变整个同色联通块更优
然后求直径，答案为$\left \lceil \frac{len}{2} \right \rceil$
因为在缩直径时，其它枝叶也会缩掉，这个感性理解即可

若某些门之间成环，则破开环中任意一扇门可以打开环中所有门
于是问题等价于n 扇门形成1-k 个环有几种方案，再除总方案数
总方案显然是$n!$
第一类斯特林数参考组合数学入门
题目还限制一号门不能单独成环，需减去一号单独成环的方案数
因此方案数为

$$\sum _{i=1}^{k}S_{n}^{i}-S_{n-1}^{i-1}$$

代码就不放了

首先将排名相同的选手放入同一个集合
这样的集合个数可以为$1-n$
集合之间相对顺序并不清楚，因此是一个全排列
第二类斯特林数参考组合数学入门
设$S\left ( n,k \right )$为$n$个元素放入$k$个非空集合的方案数
不难得出总方案数为

$$\sum_{i=1}^{n}S\left ( n,i \right )*i!$$

代码就不放了

写在前面

感觉组合数学是OI （高中数学）中比较难啃的一部分
还是得写点什么来总结一下
组合数$C,A$的有关性质这里就不赘述了，高中数学里有
水平不高，只能写一点个人的理解

题目大意：
给出一棵n 个节点的树，每条边有一个权值
若v 在u 的子树内，且$d_{u-v}\leq a_{v}$，则称u 能控制v
问每个点能控制多少点

因为v 在u 的子树内，所以$d_{u-v}=dep_{v}-dep_{u}$
化简得$dep_{v}-a_{v}\leq dep_{u}$
观察到$dep_{v}-a_{v}$为定值，且$dep_{u}$单调递增
找到第一个点u，满足$dep_{v}-a_{v}\leq dep_{u}$，则$u-v_{fa}$路径上所有点均可控制点$v$
由于只有一次询问，可用树上差分
至于怎么找第一个满足的点u，可以用二分或倍增

感觉倍增实现起来会简单一点，代码用的是二分

问题大意：
给出一棵n 个节点的树，每条边距离为1
其中有m 个节点受到了（来自东方的）神秘力量的影响
如果点x 有神秘力量来源，则距离x 小于等于d 的点均会被影响
神秘力量来源只有一个，问有几个点可能有神秘力量来源

一个节点可能有神秘力量来源，当且仅当它与所有受影响点距离均小于等于d

首先考虑求子树内的最大距离
设$f\left [ x \right ]$为点x 到子树中节点的最远距离，不难得出

$$f\left [ x \right ]=max\left \{ f\left [ x_{son} \right ]+1 \right \}$$

要保证$x_{son}$中有被神秘力量影响的节点

设$g\left [ x \right ]$为x 到非子树中节点的最远距离
对于非子树中的节点，有两种可能

• 来自兄弟节点

$$g\left [ x \right ]=max\left \{ f\left [ x_{brother} \right ]+2\right \}$$

• 来自父节点

$$g\left [ x \right ]=max\left \{ g\left [ x_{fa} \right ]+1\right \}$$

对于来自兄弟节点的转移，暴力枚举会超时
考虑用$son\left [ x \right ]$记录x 子节点中距离最大值
仅在$x=son\left [ x_{fa} \right ]$遍历所有兄弟节点

刚学OI 两个月上考场碰到这题表示一脸懵逼

每条路径$\left ( u,v \right )​$分成两条链，一条$\left ( u,LCA \right )​$，一条$\left ( LCA,v \right )​$

首先考虑$\left ( u,LCA \right )$
不难得出，当$dep_{u}-dep_{x}=w_{x}$会被观察到
观察到$dep_{x}+w_{x}$为定值，用桶统计即可
在点$u$，$cnt\left [ dep_{u} \right ]+1$
在$LCA$，$cnt\left [ dep_{u} \right ]-1$

然后是$\left ( LCA,v \right )$
同理可得，当$t_{i}-\left ( dep_{v}-dep_{x} \right )=w_{x}$会被观察到
其中$t_{i}$为$\left ( u,v \right )$的结束时间$t_{i}=dep_{u}+dep_{v}-2dep_{LCA}$
化简得$dep_{u}-2dep_{LCA}=w_{x}-dep_{x}$，仍然用桶统计
需要注意的是可能会有负值

还有，当$dep_{u}-dep_{LCA}=w_{LCA}$时，$LCA$会重复计算，记得减掉

lcm 过大无法枚举，考虑枚举gcd
对于一组$gcd\left ( x,n \right )=k$，有$gcd\left ( \frac{x}{k},\frac{n}{k} \right )=1$，且$lcm\left(x,n\right)=\frac{xn}{k}$
记

$$f\left [ k \right ]=\sum_{i=1}^{k}i\left [ gcd\left ( i,k \right )=1 \right ]$$

根据定义，若$gcd\left ( x,n \right )=1$，则$gcd\left ( n-x,n \right )=1$
因此

$$f\left [ k \right ]= \frac{k*\varphi\left [ k \right ]}{2}$$

枚举所有的k
则

$$\sum lcm\left ( x,n \right )=k*\frac{n}{k}*f\left [ \frac{n}{k} \right ]\left ( k|n,gcd\left ( x,n \right )=k \right )$$

复杂度$O\left ( T\sqrt{N} \right )$

直到有一天我被卡了，才发现有复杂度更低的做法
继续化简上式

$$\sum lcm\left ( x,n \right )=n*f\left [ \frac{n}{k} \right ]\left ( k|n,gcd\left ( x,n \right )=k \right )$$

好吧没啥区别

$$\sum_{i=1}^{n}lcm(i,n)=\sum _{d\mid n}f\left [ d \right ]*n$$

可以$O\left ( NlogN \right )$，$O\left (1 \right )$回答

根据定义，不难得出

$$LCM\left ( 1,n \right )=\prod _{p_{i}\in \mathbb{P},p_{i}\leq n}p_{i}^{\left \lfloor log_{p_{i}}n \right \rfloor}$$

筛一遍素数之后暴力统计即可

空间不够就压位筛

对于多次询问，观察到$p_{i}> \sqrt{n}$的指数均为1
可以求一遍乘积前缀和，将复杂度降为$O\left ( T\sqrt{N} \right )$

最重要的是，这题模数是$1e8+7$，不是$1e9+7$！