1.树上拓扑排序计数
结论$dfrac{n!}{prodlimits_{i=1}^n size_i}$
对于节点$i$，其子树随意排序的结果是$size[i]!$
但$i$需要排在第一位，只有$size[i]-1$个数可以任意排
乘上$frac{1}{size[i]}$
2.DAG上的问题退化成有向树解决
如果转化为DAG问题的题目，如果边与边之间有传递关系
可以退化成树进行解决
在建树的时候需要关心的是某一个点的直接父亲是什么
如ATcoder的ABC158F
3.在基环树上DP
主要思想是将基环树上的环断开，然后做树形DP
最后处理这一条边对答案的影响
4.在数列上划分并要求划分区域递增的DP
基本的DP转移是
$dp[i][j]=max{dp[j][k]}+v(i)$
其中 $i$到$j$的区间和大于 $j$到$k$的区间和
朴素复杂度$O(n^3)$
可以使用单调队列优化到$O(n^2)$
利用固定j的取值
所以$i$增加的同时，$k$的范围也相应变大，利用单调队列和单指针维护
例如P3089
但如果$v(i)$有单调性，可优化到$O(n)$，如P5665
5.求$depth[LCA(i,j)]$处理办法
将$i$到$root$的路径所有的点权值加一，然后询问$j$到$root$的路径的点权之和，就是$LCA$的深度
$LCA$可以看成两个点到根的两条链的第一个交点
6.LCT维护边权
将边看作一个点，将这个代表边的点的点权赋为这条边的边权，并将其他的点边权设为$0$或其他不影响答案的值
在连边或断边时，设这条边两端的端点为$u$,$v$，代表边的点编号为$id$
link(u,id),link(id,v);
cut(u,id),cut(id,v);
7.LCT维护子树信息
维护一个点由虚边连结的点的信息$si$，然后再维护所有的边（包括虚边和$Splay$上左右儿子）相连的儿子和自己的信息$s$
因为虚实边会随着LCT的操作不断变化
首先在$pushup$的时候，$s[x]=s[son[x][0]]+s[son[x][1]]+si[x]+val[x]$，保证$s$的值实时更新
$access$的时候因为去掉了$x$之前的实儿子（变为了虚儿子），增加了一个新的实儿子（由原来虚儿子变来），$si$一加一减，$s$不变化
for (int y=0;x;x=fa[x]) { splay(x); si[x]+=s[son[x][1]]; son[x][1]=y; si[x]-=s[son[x][1]]; pushup(x); y=x; }//access
在$link$的时候增加了一条虚边，改变$y$的$si$，要注意要将$y$转到根上，以免改变其他节点的值
inline void link(int x,int y) { makeroot(x); access(y); splay(y); fa[x]=y; si[y]+=s[x]; pushup(y); }
$cut$因为切掉的是实边，对$si$无影响，注意$pushup$即可
还有这里可以维护的信息是满足加减性的，如子树大小，子树权值和
但像子树权值最大值是不满足加减性的，不能维护（据说可以每个节点将$si$和$s$改成一棵平衡树）
在求出$x$子树的信息的时候，$access(x)$后取出$si[x]$即可
8.维护区间中位数
可以二分答案，将$>=x$的数标记为$1$，$<x$的数标记为$-1$，利用维护区间和，若某一个区间的和大于$0$，则这个区间的中位数$>=$当前二分的数，若某一个区间的和小于$0$，则这个区间的中位数$<=$当前二分的数
9.对于题目条件限制的转化
对于一些要求最大最小值的题目，然后题目对选择（操作）集合有限制的，比如取$min$,$max$操作，那么可以试图构造出一个原集合的一个超集（相当于将题目条件变弱），使得超集中的每一个元素都存在原集合中的元素比它更优或相同。简单来说就是放宽题目条件，使问题更加好处理，虽然可能将题目条件放宽之后，有一部分元素不合法，但这些元素都能在原集合中找到比它更好的元素出来，所以这些元素不会变成答案
例如AGC28C
10.树上任意一点的最远距离
树上任意一点的最远距离就是树上直径的两个端点到该点距离的最大值
证明：利用反证法
对于一条直径两个端点$u$,$v$
若存在一条路径$x->y$，且满足$len(x,y)>len(x,u)$,$len(x,y)>len(x,v)$
设直径和路径的交点为$a$
则可以找到一条比原来直径更长的路径$u->a->y$
与直径的定义矛盾
11.树联通块直径合并
两个树联通块合并之后，直径的两端点一定在原来两个联通块的直径的四个端点内
然后在这四个端点处枚举即可，判断剩余两个点是否在选出的两个点形成的路径上
$P.S.$ 判断一个点在一条路径上的充分必要条件是
设路径为$x->y$，当前要判断的点为$u$
那么$depth[u]>=depth[LCA(x,y)]$并且 $LCA(u,x)=u$或$LCA(v,x)=v$
12.$sigma$因数函数
性质：
$$sigma _{0}(i*j)=sum_{xmid i}sum_{ymid j}[gcd(i,j)=1]$$
多维情况
$$sigma_k (AB) = sum_{x|A} sum_{y|B} [gcd(x,y)=1] (x frac{B}{y})^k = sum_{x|A} sum_{y|B} [gcd(x,frac{B}{y})=1] (x y)^k$$
三个因数相乘情况
$$sigma_k (ABC) = sum_{x|A} sum_{y|B} sum_{z|C} [gcd(x,frac{B}{y})=1] [gcd(y,frac{C}{z})=1] [gcd(x, frac{C}{z}=1)] (x y z)^k$$
证明待填……