题解思路与方法

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

问题分析

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

题目内容

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

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

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

【名词解释】

• 树:树是一个无环连通图。
• 连通分量:连通分量指在图中任意两个顶点都可以互相到达的最大顶点集合。
• 删除:删除操作指将指定的城市摧毁，并移除该城市及与其相关的所有道路。
• 安全分数:安全分数指删除一个城市后，剩余各连通分量中，取各分量内防御值最大值的和。

输入描述

第一行输入一个整数$n(2≦n≦10^5)$，表示城市的数量。

第二行输入$n$个整数$a_1,a_2,...,a_n(0≦a_i≦10^9)$，表示每个城市的防御值。

接下来$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