题目内容

在一个由$n$个城市构成的王国中，城市之间由道路相连，且构成一棵树。每个城市都有一个防御 值，用以表示其抵御敌人攻击的能力。

当敌人摧毁其中一个城市后，剩余的城市会被分成若干个连通分量。对于每个连通分量,我们定义其【安全指标】为该分量内所有城市防御值的最大值。王国的【安全分数】定义为所有连通分量安全指标的累加和。

现请你帮助国防军统计:当摧毁城市$i$后，剩余王国的安全分数。注意，每次询问都是独立的，即每次询问后，城市不会被摧毁。

【名词解释】

题解思路与方法

这道题要求我们在摧毁一个城市后，计算剩余城市的安全分数。安全分数是指每个连通分量中防御值的最大值的总和。题目给定的是一棵树结构，我们需要高效地计算每个节点被删除后，剩余树的安全分数。

问题分析

1. 树的结构与性质：树是一个无环连通图，每两个城市之间有一条唯一的路径。
2. 摧毁城市后的安全分数计算：
   • 每摧毁一个城市后，树会被分成若干个连通分量。
   • 每个连通分量的安全指标是该连通分量内防御值的最大值。