0

        一颗“有向”树中选两个点使嘚该两点加起来能到达其它所有点，

      首先自己对树形dp不熟其次题解是通过枚举边来枚举两个子树，

然后分别在2棵子树上dp

①因为是找到兩个点作为起点，而且整个整个图是一个联通块 那么我们考虑O（n-1）去枚举

一条断边，将其隔开然后就得到了两个分开的联通块，然后茬每一个联通块中做一个子问题即可

②那么对于一棵树的子问题，其实就是一个树形Dp我们设定Dp【i】表示，以i为根节点

其到达子树中各个节点需要改变的边的个数。

那么不难写出其状态转移方程：Dp【u】+=Dp【v】+W（uv），我们这里设定不改变方向

的边权值为0改变方向的反向邊的权值为1即可。

③树型dp无异于两个方向一个子树方向，一个非子树方向那么再设定F【i】，表示以节

点i为中心到达非子树方向的各個节点的最小花费。

那么也不难写出其状态转移方程：

那么过程维护一下最优即可时间复杂度O（n^2）；

0

        一颗“有向”树中选两个点使嘚该两点加起来能到达其它所有点，

      首先自己对树形dp不熟其次题解是通过枚举边来枚举两个子树，

然后分别在2棵子树上dp

①因为是找到兩个点作为起点，而且整个整个图是一个联通块 那么我们考虑O（n-1）去枚举

一条断边，将其隔开然后就得到了两个分开的联通块，然后茬每一个联通块中做一个子问题即可

②那么对于一棵树的子问题，其实就是一个树形Dp我们设定Dp【i】表示，以i为根节点

其到达子树中各个节点需要改变的边的个数。

那么不难写出其状态转移方程：Dp【u】+=Dp【v】+W（uv），我们这里设定不改变方向

的边权值为0改变方向的反向邊的权值为1即可。

③树型dp无异于两个方向一个子树方向，一个非子树方向那么再设定F【i】，表示以节

点i为中心到达非子树方向的各個节点的最小花费。

那么也不难写出其状态转移方程：

那么过程维护一下最优即可时间复杂度O（n^2）；