HNOI2022 树上问题

本文主要是介绍HNOI2022 树上问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

考点

• 基环树
• 树链剖分
• 树上DP
• 树上分治

点分治

NOTE
1.分治前求dep的时候忘记dep[rt]=0

流程1(适用于计数等容易去重的)

• 找根
• 处理过当前根到子树内的路径(加入根到根的路径，用两条到根的路径合并)
• 去掉不合法(统计同一个子树出来到当前根的两条路径)，继续分治

流程2(适用于最优化等难以去重的)

• 找根
• 类似树型DP，一个子树一个子树处理经过当前点的路径
• 分治下去

trick

1. 套 \(BIT\) ,对路径长度 \(\le\) k的路径计数 P4178 Tree
2. 树上路径二维偏序，用流程一搞出所有路径，然后按一维排序，另一维用 \(BIT\) 做二维偏序即可。
3. 一些利用点分治来移动最优点的题，要注意对 vis[v] 的判断 P4886 快递员

这篇关于HNOI2022 树上问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！