Tree in Graph

树是图的一种特殊形式，图中的树也是比较难的一类问题。

树形图

有一类特殊的图，本质上是树，但是以图的形式给出，通常涉及不同子树的特征值计算。这种图本质上是树，无环。通常顶点是n个，边的个数是n-1个，无环，每个顶点都可以成为树的根，边有权重。通常是求解与顶点连通的子树的特征值。

通常需要用到乘法原理。

第一步，把问题分解为根和子树的问题，需要以每个顶点为根，子树就是与其相邻的顶点为根的子树，这种根+子树的组合就是一个子问题；

第二步，乘法原理。每个「子树」会得到一个数量，子问题的结果就用到乘法原理来求得：

第三步，对于每个子树，用其他方法得到需要的「数量」值。这个不同的问题不一样。但本质上，要么是连通分量问题（可用并查集），要么是路径问题。因为这是在一个子树上面的问题，相当于树的问题，通常DFS可求得结果。