很精巧的题。
很明显求的是虚树的叶子结点数量。
然而这个玩意还带修,看起来有点恶心。不过带修的问题一般都不会很复杂,再加上子树修改我们考虑用搜索序把树拍到序列上,为了更好的刻画叶子,我们可以考虑使用性质更强的欧拉序,而对于欧拉序我们不妨放在括号串上考虑,叶子在串中相当于一个子串 ()
,维护这个东西可以直接放到线段树上就做完了,时间复杂度 \(\mathcal{O}(n+q\log n)\),代码。
很精巧的题。
很明显求的是虚树的叶子结点数量。
然而这个玩意还带修,看起来有点恶心。不过带修的问题一般都不会很复杂,再加上子树修改我们考虑用搜索序把树拍到序列上,为了更好的刻画叶子,我们可以考虑使用性质更强的欧拉序,而对于欧拉序我们不妨放在括号串上考虑,叶子在串中相当于一个子串 ()
,维护这个东西可以直接放到线段树上就做完了,时间复杂度 \(\mathcal{O}(n+q\log n)\),代码。