思路总览

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

关键记号

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

  

题目内容

给定一棵以节点 $1$ 为根的树，树上共有 $n$ 个节点，其中某些节点被标记为"红点"。每条边 $(u,v)$ 具有正整数权重 $w_{uv}$ 。

接下来有 $q$ 次操作，每次操作有两种类型：

1.切换节点 $v$ 的红点状态(若为红点则变为非红点，反之亦然)

2.查询节点 $v$ 到所有当前红点的带权距离之和 $S_v$ 。