本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp
做法是枚举每一条边,删除它,然后得到删除这条边的答案,再更新最后的答案
所以枚举答案的复杂度是O(n)
要做两次dfs,每个dfs其实就是遍历一次整个树,所以两次dfs的复杂度也是O(n)
所以整个算法的复杂度是O(n),但是常数应该是很大的,因为每到达一个点
更新很多信息
两次dfs都是以1为根,向下dfs的
- dfs1是递归回溯的时候更新信息,所以是一个 自底向上 的更新
- dfs2是递归下去的时候传递信息,所以是一个 自顶向下 的更新
主要记录的信息
1 | int leaf[N][3],idl[N][3]; |
怎么更新答案?
找到一条边u->v,在树中u是v的父亲
树断裂为两个部分,先算点v为子树的那部分的最长链
显然是Max[v]
之后是算点u,以及点u余下的其他儿子分支,以及u的上方,这3部分的最长链
这3部分用文字很难描述,主要看dfs2里面的所有更新
代码中奖所有更新都用函数来写
void updata_xxxxx() 这样的函数都是更新函数,xxxx就是对应要更新的数组
//最后,我觉得正解可能比我想的简单,我觉得我想复杂了,但是现在还没有想出简单的更新
1 |
|