#P2899. 第3题-城市王国
          
                        
                                    
                      
        
              - 
          
          
                      1000ms
            
          
                      Tried: 13
            Accepted: 6
            Difficulty: 7
            
          
          
          
                       所属公司 : 
                              阿里
                                
            
                        
              时间 :2025年4月24日-阿里云(算法岗)
                              
                      
          
 
- 
                        算法标签>树形DP          
 
第3题-城市王国
题解思路与方法
这道题要求我们在摧毁一个城市后,计算剩余城市的安全分数。安全分数是指每个连通分量中防御值的最大值的总和。题目给定的是一棵树结构,我们需要高效地计算每个节点被删除后,剩余树的安全分数。
问题分析
- 树的结构与性质:树是一个无环连通图,每两个城市之间有一条唯一的路径。
 - 摧毁城市后的安全分数计算:
- 每摧毁一个城市后,树会被分成若干个连通分量。
 - 每个连通分量的安全指标是该连通分量内防御值的最大值。
 - 整个王国的安全分数是所有连通分量安全指标的和。
 
 
解题思路
- 
树形 DP:
- 我们可以采用树形动态规划的思路来解决这个问题。首先从根节点开始,计算每个节点的子树中的防御值最大值(down)。
 - 然后再从根节点出发,计算每个节点向上(父节点侧)经过的防御值最大值(up)。
 
 - 
算法步骤:
- 第一次 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≦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