1000ms

Difficulty: 10

所属公司 : 美团

时间 :2025年8月23日-算法岗

算法与标签>树

会员或题库专享

请先，开通会员或购买题库美团机考编程题库，可解锁完整内容。

购买美团机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

思路总览

核心目标：在动态切换活跃节点的同时，高效回答“到所有活跃节点距离之和”。直接维护会超时，因此使用点分治配合分层距离与分组前缀量维护。

关键记号

用点分治把树分成若干层重心。对每个原树节点 $u$ ，记录它到每一层重心的距离序列：

题目内容

在一棵由 $n$ 个节点构成的树上，节点编号为 $1$ 到 $n$ ，每条边都有一个正整数权重。每个节点可以是“活跃”或“非活跃”状态。

你需要处理 $q$ 个操作，操作类型如下：

切换某个节点 $v$ 的活跃状态（若当前为活跃则变为非活跃，反之亦然）；
查询某个节点 $v$ 到当前所有活跃节点的距离之和。

节点间的距离定义为连接两点的唯一简单路径上所有边的权重之和。

请对所有类型 $2$ 的操作输出对应的结果。