fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class Main {
  5.     static List<Integer>[] tree;
  6.     static char[] color;
  7.     static long[] weight;
  8.     static long minCost = Long.MAX_VALUE;
  9.  
  10.     public static void main(String[] args) throws IOException {
  11.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  12.         int n = Integer.parseInt(br.readLine());
  13.         color = br.readLine().trim().toCharArray();
  14.         weight = new long[n];
  15.         StringTokenizer st = new StringTokenizer(br.readLine());
  16.         for (int i = 0; i < n; i++) {
  17.             weight[i] = Long.parseLong(st.nextToken());
  18.         }
  19.  
  20.         tree = new ArrayList[n];
  21.         for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();
  22.         for (int i = 0; i < n - 1; i++) {
  23.             st = new StringTokenizer(br.readLine());
  24.             int u = Integer.parseInt(st.nextToken()) - 1;
  25.             int v = Integer.parseInt(st.nextToken()) - 1;
  26.             tree[u].add(v);
  27.             tree[v].add(u);
  28.         }
  29.  
  30.         // 遍历每个节点作为可能的根节点
  31.         for (int root = 0; root < n; root++) {
  32.             char target = color[root];
  33.             long[] totalCost = new long[1];
  34.             boolean[] visited = new boolean[n];
  35.             dfs(root, -1, target, totalCost, visited);
  36.             minCost = Math.min(minCost, totalCost[0]);
  37.         }
  38.  
  39.         System.out.println(minCost);
  40.     }
  41.  
  42.     // 返回该子树是否需要修改
  43.     static boolean dfs(int node, int parent, char target, long[] totalCost, boolean[] visited) {
  44.         visited[node] = true;
  45.         boolean needModify = (color[node] != target);
  46.         long subtreeWeight = weight[node];
  47.  
  48.         for (int child : tree[node]) {
  49.             if (child != parent && !visited[child]) {
  50.                 boolean childNeedModify = dfs(child, node, target, totalCost, visited);
  51.                 if (childNeedModify) {
  52.                     needModify = true;
  53.                     // 子节点需要修改，其权值已在递归中累加
  54.                 } else {
  55.                     subtreeWeight += weight[child]; // 仅累加不需要修改的子树的权值
  56.                 }
  57.             }
  58.         }
  59.  
  60.         if (needModify && parent != -1) { // 非根节点需要修改时才累加
  61.             totalCost[0] += subtreeWeight;
  62.         }
  63.         return needModify;
  64.     }
  65. }
Success #stdin #stdout 0.09s 55088KB
comments (?)
stdin
copy 
3
RBB
1 2 3
1 2
2 3
stdout
copy 
1
https://ideone.com/CvQJ5G
language:
Java (HotSpot 12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!