————我会出手

树的常见做法

树形dp

两次dp转移

树上背包


lca + 树上差分
树的两条路径相交的话

其中一条路径的lca 必然在另一个个路径上
求解一个点是否在一条路径上可以使用lca求距离即可
dist(a,b) = dist(a,x) + dist(x,b) -> x在a b 路径中

一个点x到一条路径(a,b)的最短路
d = (dist(a,x) + dist(b,x) - dist(a,b))/2;
对式子操作，同时做树形dp可以得到路径在所有点之间的距离

DSU on tree
离线的子树问题，通过对儿子节点的统计可以得出父节点的答案

树上主席树
只用来解决子树类型的问题

树链剖分
对于树上的路径修改,同时可以对子树修改

从树上固定点判断是否出现排列,(多重集合是否相等)
可以使用随机哈希，然后从路径开始搜索即可

树上结合两点的性质题,我们可以考虑当前节点和父节点的关系，我的儿子节点和儿子节点的关系,要有一种划分的方式去概括同时可以继承不重不漏

基环树
注意有些时候需要处理自环,处理入度为0的点这样剩下的就是在环上面的情况

图一般来说都是考察各种各样的最短路,及其变式,t


图转成树来操作
一般使用tarjan来操作


1.分层图 + 路径输出

如果题目中出现了要让谁最小，或者推理出来了要让谁最小的话，那这个点的某个状态结果应该就是最短路的结果，同时注意到可能存在多源最短路,或者是虚拟源点

接着如果说有些奇怪的东西例如,一个点有多个状态或者说在路程
中可以xx之类的都是表示是可以进行类似分层图的操作

同时注意到分层图的初始状态，在路径输出的时候应该是由初始点的初始状态定义的而不是初始点


2.图论 + dp 计数或者带有转移性质

一般而言要和topsort结合,这样的dp是无后效性的也就是才可以dp的

或者是最短路的数量，一般而言是直接在最短路上操作

3.反过来建图，有些时候我们正向建图得到的东西和我们要求的东西是有点对立的,这个时候考虑反过来建图,看是否能解决问题

4.利用tarjan 变成topsort性质,然后重新建图进行dp
  利用tarjan建立圆方树然后通过圆方树来使用树上的性质