题解思路与方法
这道题要求我们在摧毁一个城市后，计算剩余城市的安全分数。安全分数是指每个连通分量中防御值的最大值的总和。题目给定的是一棵树结构，我们需要高效地计算每个节点被删除后，剩余树的安全分数。
问题分析
- 树的结构与性质：树是一个无环连通图，每两个城市之间有一条唯一的路径。
- 摧毁城市后的安全分数计算：
P2899.第3题-城市王国
题目内容
在一个由n个城市构成的王国中，城市之间由道路相连，且构成一棵树。每个城市都有一个防御
值，用以表示其抵御敌人攻击的能力。
当敌人摧毁其中一个城市后，剩余的城市会被分成若干个连通分量。对于每个连通分量,我们定义其【安全指标】为该分量内所有城市防御值的最大值。王国的【安全分数】定义为所有连通分量安全指标的累加和。
现请你帮助国防军统计:当摧毁城市i后，剩余王国的安全分数。注意，每次询问都是独立的，即每次询问后，城市不会被摧毁。
【名词解释】
- 树:树是一个无环连通图。
- 连通分量:连通分量指在图中任意两个顶点都可以互相到达的最大顶点集合。
- 删除:删除操作指将指定的城市摧毁，并移除该城市及与其相关的所有道路。
- 安全分数:安全分数指删除一个城市后，剩余各连通分量中，取各分量内防御值最大值的和。
输入描述
第一行输入一个整数n(2≦n≦105)，表示城市的数量。
第二行输入n个整数a1,a2,...,an(0≦ai≦109)，表示每个城市的防御值。
接下来n−1行，每行输入两个整数u,v(1≦u,v≦n,u=v)，表示城市u与城市v之间有一条道路，保证所有城市构成一棵树。
输出描述
输出共一行，包含n个整数，依次表示当摧毁城市1,2,...,n后，剩余王国的安全分数，数字间以空格
分隔。
样例1
输入
5
3 2 5 4 1
1 2
1 3
3 4
3 5
输出
7 5 8 5 5
说明
在这组样例中，依次摧毁每个城市后，剩余王国的安全分数分别为:
-
当摧毁城市1后，剩余的城市构成两个连通分量:{2}和{3,4,5}。
- 连通分{2}的安全指标为2;
- 连通分量{3,4,5}的安全指标为max{5,4,1}=5;
- 整个王国的安全分数为2+5=7。
-
当摧毁城市2后，剩余城市为{1,3,4,5}，整体连通，其安全指标为max{3,5,4,1}=5。
-
当摧毁城市3后，剩余城市被分为三个连通分量:{1,2}、{4}与{5}。
- 连通分量{1,2}的安全指标为max{3,2}=3;
- 连通分量{4}的安全指标为4；
- 连通分量{5}的安全指标为1;
- 安全分数为3+4+1=8。
-
当摧毁城市4或5后，其余城市均构成一个连通分量，安全分数均为max{3,2,5,1}=5。
样例2
输入
5
5 1 2 10 3
1 2
2 3
3 4
4 5
输出
10 15 15 8 10
