题解思路与方法

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

问题分析

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

解题思路

1. 树形 DP：

   • 我们可以采用树形动态规划的思路来解决这个问题。首先从根节点开始，计算每个节点的子树中的防御值最大值（down）。
   • 然后再从根节点出发，计算每个节点向上（父节点侧）经过的防御值最大值（up）。

2. 算法步骤：

   • 第一次 DFS（down DP）：从树的根节点出发，计算每个子树中的防御值最大值。
   • 第二次 DFS（up DP）：再从根节点出发，计算每个节点的“父侧”部分的防御值最大值。
   • 对于每个节点被摧毁后，安全分数就是将其子树的最大防御值（down）与父侧的最大防御值（up）相加。

复杂度分析

• 时间复杂度：每个 DFS 遍历一次树，每个节点和边只访问一次，因此时间复杂度是 O(n)，其中 n 是城市的数量。
• 空间复杂度：我们需要存储树的邻接表、每个节点的防御值和 DP 数组，因此空间复杂度是 O(n)。

Python 代码

import sys
sys.setrecursionlimit(10 ** 6)  # 递归深度限制
def destroy_city(n, defense_values, roads):
    # 构建邻接表
    adj = [[] for _ in range(n)]
    for u, v in roads:
        adj[u-1].append(v-1)
        adj[v-1].append(u-1)

    # 初始化 DP 数组
    down = [0] * n  # down[i]：以 i 为根的子树中的最大防御值
    up = [0] * n    # up[i]：i 节点的父侧的最大防御值
    ans = [0] * n   # 存储最终结果

    # 第一次 DFS：计算 down 数组
    def dfs_down(u, parent):
        down[u] = defense_values[u]  # 初始的 down[u] 就是自己节点的防御值
        for v in adj[u]:
            if v == parent:
                continue
            dfs_down(v, u)
            down[u] = max(down[u], down[v])  # 更新 down[u] 为子树最大防御值

    # 第二次 DFS：计算 up 数组并求解安全分数
    def dfs_up(u, parent):
        nonlocal ans
        # 计算当前节点摧毁后的安全分数
        ans[u] = up[u]

        # 上面的最大值
        up_mx = max(up[u],defense_values[u])  

        # 子树的最大值和次大值
        mx1,mx2 = -1,-1

        for v in adj[u]:
            if v == parent:
                continue
            ans[u] += down[v]  # 当前节点摧毁后的安全分数是父侧 + 子树的最大防御值
            if down[v] > mx1:
                mx2 = mx1
                mx1 = down[v]
            elif down[v] > mx2:
                mx2 = down[v]
        
        # 更新子节点的 up 值
        for v in adj[u]:
            if v == parent:
                continue
            if down[v] == mx1:
                up[v] = max(up_mx, mx2)
            else:
                up[v] = max(up_mx, mx1)
            dfs_up(v, u)

    # 初始 DFS 计算 down 数组
    dfs_down(0, -1)

    # 初始 DFS 计算 up 数组，并求解安全分数
    dfs_up(0, -1)

    return ans


def main():
    # 读取输入
    n = int(input())  # 城市数量
    defense_values = list(map(int, input().split()))  # 城市防御值
    roads = []
    
    for _ in range(n - 1):
        u, v = map(int, input().split())  # 每条道路连接的城市
        roads.append((u, v))

    # 计算结果
    result = destroy_city(n, defense_values, roads)

    # 输出结果
    print(" ".join(map(str, result)))


# 调用主函数
if __name__ == "__main__":
    main()

C++代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
vector<int> defense;
vector<vector<int>> adj;
vector<int> down_dp, up_dp;
vector<ll> ans;

void dfs_down(int u, int p) {
    down_dp[u] = defense[u];
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs_down(v, u);
        down_dp[u] = max(down_dp[u], down_dp[v]);
    }
}

void dfs_up(int u, int p) {
    // 先累加父侧的 up 值
    ll res = up_dp[u];
    // 统计当前节点的子树 down 值之和与最大／次大
    int mx1 = -1, mx2 = -1;
    for (int v : adj[u]) {
        if (v == p) continue;
        res += down_dp[v];
        if (down_dp[v] > mx1) {
            mx2 = mx1;
            mx1 = down_dp[v];
        } else if (down_dp[v] > mx2) {
            mx2 = down_dp[v];
        }
    }
    ans[u] = res;

    // 计算子节点的 up 值并递归
    int use_up = max(up_dp[u], defense[u]);
    for (int v : adj[u]) {
        if (v == p) continue;
        int best = (down_dp[v] == mx1 ? mx2 : mx1);
        up_dp[v] = max(use_up, best);
        dfs_up(v, u);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    defense.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> defense[i];
    }
    adj.assign(n, {});
    for (int i = 0, u, v; i < n-1; i++) {
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    down_dp.assign(n, 0);
    up_dp.assign(n, 0);
    ans.assign(n, 0);

    dfs_down(0, -1);
    dfs_up(0, -1);

    // 输出
    for (int i = 0; i < n; i++) {
        cout << ans[i] << (i+1<n ? ' ' : '\n');
    }
    return 0;
}

java代码

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int[] defense;
    static List<Integer>[] adj;
    static int[] down, up;
    static long[] ans;

    static void dfsDown(int u, int p) {
        down[u] = defense[u];
        for (int v : adj[u]) {
            if (v == p) continue;
            dfsDown(v, u);
            down[u] = Math.max(down[u], down[v]);
        }
    }

    static void dfsUp(int u, int p) {
        // 父侧 up 值
        long sum = up[u];
        int mx1 = -1, mx2 = -1;
        for (int v : adj[u]) {
            if (v == p) continue;
            sum += down[v];
            if (down[v] > mx1) {
                mx2 = mx1;
                mx1 = down[v];
            } else if (down[v] > mx2) {
                mx2 = down[v];
            }
        }
        ans[u] = sum;

        int useUp = Math.max(up[u], defense[u]);
        for (int v : adj[u]) {
            if (v == p) continue;
            int best = (down[v] == mx1 ? mx2 : mx1);
            up[v] = Math.max(useUp, best);
            dfsUp(v, u);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine().trim());
        defense = new int[n];
        down = new int[n];
        up = new int[n];
        ans = new long[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            defense[i] = Integer.parseInt(st.nextToken());
        }
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()) - 1;
            int v = Integer.parseInt(st.nextToken()) - 1;
            adj[u].add(v);
            adj[v].add(u);
        }

        dfsDown(0, -1);
        dfsUp(0, -1);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(ans[i]);
            if (i + 1 < n) sb.append(' ');
        }
        System.out.println(sb);
    }
}

题目内容

在一个由$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