fork download 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class Main {
  5.     static List<Integer>[] tree;
  6.     static char[] colors;
  7.     static long[] weights;
  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.         colors = br.readLine().trim().toCharArray();
  14.         weights = new long[n];
  15.         StringTokenizer st = new StringTokenizer(br.readLine());
  16.         for (int i = 0; i < n; i++) {
  17.             weights[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 = colors[root];
  33.             long[] sum = new long[1];
  34.             boolean valid = dfs(root, -1, target, sum);
  35.             if (valid) {
  36.                 minCost = Math.min(minCost, sum[0]);
  37.             }
  38.         }
  39.  
  40.         System.out.println(minCost);
  41.     }
  42.  
  43.     // 返回是否需要修改该子树，并累加代价
  44.     static boolean dfs(int node, int parent, char target, long[] sum) {
  45.         boolean needModify = (colors[node] != target);
  46.         for (int child : tree[node]) {
  47.             if (child == parent) continue;
  48.             boolean childNeed = dfs(child, node, target, sum);
  49.             if (childNeed) {
  50.                 needModify = true; // 如果子节点需要修改，则当前节点必须被覆盖
  51.             }
  52.         }
  53.         if (needModify) {
  54.             sum[0] += weights[node];
  55.         }
  56.         return needModify;
  57.     }
  58. }
Success #stdin #stdout 0.08s 55020KB
comments (?)
stdin 
3
RBB
1 2 3
1 2
2 3
stdout 
3
https://ideone.com/ZyrHxk
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!