fork download 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static int n;
  5.     static char[] color;
  6.     static long[] weight;
  7.     static List<Integer>[] tree;
  8.     static boolean[] visited;
  9.  
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  12.         n = sc.nextInt();
  13.  
  14.         color = sc.next().toCharArray();
  15.         weight = new long[n + 1];
  16.         for (int i = 1; i <= n; i++) {
  17.             weight[i] = sc.nextLong();
  18.         }
  19.  
  20.         tree = new ArrayList[n + 1];
  21.         for (int i = 1; i <= n; i++) {
  22.             tree[i] = new ArrayList<>();
  23.         }
  24.         for (int i = 1; i < n; i++) {
  25.             int u = sc.nextInt();
  26.             int v = sc.nextInt();
  27.             tree[u].add(v);
  28.             tree[v].add(u);
  29.         }
  30.  
  31.         long res = Long.MAX_VALUE;
  32.         for (int root = 1; root <= n; root++) {
  33.             char targetColor = color[root - 1];
  34.             visited = new boolean[n + 1];
  35.             long cost = dfs(root, -1, targetColor);
  36.             res = Math.min(res, cost);
  37.         }
  38.  
  39.         System.out.println(res);
  40.     }
  41.  
  42.     // 计算以当前节点为根的子树变为目标颜色的总代价
  43.     static long dfs(int u, int parent, char targetColor) {
  44.         visited[u] = true;
  45.         long cost = 0;
  46.         if (color[u - 1] != targetColor) {
  47.             cost += weight[u];
  48.         }
  49.         for (int v : tree[u]) {
  50.             if (v != parent && !visited[v]) {
  51.                 cost += dfs(v, u, targetColor);
  52.             }
  53.         }
  54.         return cost;
  55.     }
  56. }
  57.  
Success #stdin #stdout 0.14s 54548KB
comments (?)
stdin 
3
RBB
1 2 3
1 2
2 3
stdout 
1
https://ideone.com/QDwXI7
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!