F. 1-1-1, Free Tree!

问题描述

给定一棵有 $n$ 个顶点的树，顶点编号从 1 到 $n$ 。每个顶点都有一个初始颜色 $a_i$ 。

树的每条边由三个数定义： $u_i$ 、 $v_i$ 和 $c_i$ ，其中 $u_i$ 和 $v_i$ 是边的端点， $c_i$ 是边的参数。边的成本定义如下：如果顶点 $u_i$ 和 $v_i$ 的颜色相同，则成本为 0；否则，成本为 $c_i$ 。

你还会收到 $q$ 个查询。每个查询的形式为：将顶点 $v$ 重新着色为 $x$ 。查询是相互依赖的（每次查询后，颜色变化会保留）。每次查询后，你需要输出树中所有边的成本之和。

这个问题的核心挑战是快速回答查询。一种朴素的方法是在每次查询后重新计算整个树的边成本。这将涉及检查所有 n-1 条边，使得每次查询耗时 O(n)。由于查询次数高达 2 * 10^5，这种 O(n*q) 的方法会太慢。

关键的洞察是，当我们重新着色单个顶点 v 时，成本只会改变与 v 直接相连 的边的成本。树中所有其他边的成本保持不变。因此，我们可以只计算总成本的 变化量，而不是重新计算所有东西。

让我们一步步分解这个高效的方法。

为了有效地处理更新，我们首先需要给树一些结构并准备一些数据。

将树定根： 我们任意指定一个顶点（比如顶点1）作为根。这为树赋予了父子层次结构，这非常有帮助。
深度优先搜索 (DFS)： 我们从根开始执行一次DFS遍历。在这次遍历中，我们将为每个顶点 v 填充两个关键信息：
- parent[v]: 顶点 v 的父节点。
- cost_to_parent[v]: 连接 v 与其父节点的边的参数 c。
核心数据结构 (mem map)： 这是解决方案中最重要的部分。对于每个顶点 v，我们需要知道连接到其子节点的边的成本，并按子节点的颜色分组。map（或哈希映射/字典）非常适合这个任务。
- 对于每个顶点 v，我们创建一个map，称之为 mem[v]。
- mem[v][color] 将存储所有颜色为 color 的 v 的子节点的边参数之和。
例如，如果顶点 v 有三个子节点 u1、u2 和 u3，颜色分别为 red、blue 和 red，边参数分别为 c1、c2 和 c3，那么 mem[v] 的map将如下所示：
- mem[v][red] = c1 + c3
- mem[v][blue] = c2
这个map也是在初始的DFS中构建的。

DFS之后，我们拥有了所有必要的信息。我们通过遍历所有非根顶点 v 来计算树的初始总成本，我们称之为 total_ans，并检查：

if color[v] != color[parent[v]]: total_ans += cost_to_parent[v]

这让我们在 O(n) 时间内得到了正确的初始成本。

现在，让我们考虑一个查询：“将顶点 v 重新着色为 x”。设 v 的原始颜色为 old_color。

我们只需要通过考虑连接到 v 的边来调整 total_ans。

从 0 到 C： 改变之前，v 的颜色是 old_color。任何 v 的子节点 u 如果颜色也是 old_color，则对成本的贡献为 0（因为 color[v] == color[u]）。在 v 被重新着色为 x 后（假设 x != old_color），这些边现在有了成本。这些新“激活”的边的总成本是它们的参数之和。我们已经预先计算了这个和：它就是 mem[v][old_color]。
- 操作： total_ans += mem[v][old_color]
从 C 到 0： 改变之前，任何 v 的子节点 u 如果颜色是 x，则其边成本已计入总成本（因为 color[v] = old_color != x）。在 v 被重新着色为 x 后，这些边的成本现在为 0。这些新“停用”的边的总成本是 mem[v][x]。
- 操作： total_ans -= mem[v][x]

这两个操作，利用我们的 mem map，可以在常数时间内（或 O(log k)，其中 k 是不同子节点颜色的数量，这非常快）更新所有子节点边的贡献。

这只涉及一条边（除非 v 是根节点）。设 p = parent[v] 且 w = cost_to_parent[v]。

移除旧成本： 我们首先确定这条边在改变之前是否对成本有贡献。如果有，即 color[p] != old_color，我们从总成本中减去它的成本。
- 操作： if color[p] != old_color: total_ans -= w
添加新成本： 然后我们确定这条边在改变之后是否对成本有贡献。如果有，即 color[p] != x，我们将其成本加到总成本中。
- 操作： if color[p] != x: total_ans += w

v 颜色改变会影响其父节点 p。具体来说，它改变了边 (p, v) 在父节点 mem map 中所属的颜色组。

权重为 w 的边 (p,v) 不再与颜色为 old_color 的子节点关联。
- 操作： mem[p][old_color] -= w
边 (p,v) 现在与颜色为 x 的子节点关联。
- 操作： mem[p][x] += w

最后，我们更新实际的颜色数组：color[v] = x。

完成这些步骤后，total_ans 就保存了新的正确的总成本，我们将其输出。

通过预先计算父节点指针和 mem map，我们只需查看顶点 v、其父节点及其子节点，即可处理每个查询。使用map可以实现 O(log n) 的更新。

这是非常高效的，并且可以轻松满足问题的时间限制。