Java教程

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 树上问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航