Posted in: 解题报告

HNOI 2018 省队集训 Day 1 – 解题报告

A - Tree

这道题粗看需要 Link Cut Tree,其实不然:如果我们仍然在把节点 $1$ 作为根节点来处理子树信息、放入线段树,之后的询问我们只需要灵活的分类讨论即可。在实根为 $root$ 时,$u, v$ 之间的 $LCA$ 显然是 $lca(u, v), lca(root, u), lca(root, v)$ 之间深度最大的那一个。而修改权值和查询权值,只需要讨论两种祖先关系和平行关系即可。

Back to Top