fork download
copy 
  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.  
  9.     static long dfs(int u, int parent, char targetColor) {
  10.         long cost = 0;
  11.         if (color[u] != targetColor) cost += weight[u];
  12.         for (int v : tree[u]) {
  13.             if (v != parent) {
  14.                 cost += dfs(v, u, targetColor);
  15.             }
  16.         }
  17.         return cost;
  18.     }
  19.  
  20.     public static void main(String[] args) {
  21.         Scanner sc = new Scanner(System.in);
  22.         n = sc.nextInt();
  23.  
  24.         color = (" " + sc.next()).toCharArray(); // 1-index
  25.         weight = new long[n + 1];
  26.         for (int i = 1; i <= n; i++) {
  27.             weight[i] = sc.nextLong();
  28.         }
  29.  
  30.         tree = new ArrayList[n + 1];
  31.         for (int i = 1; i <= n; i++) tree[i] = new ArrayList<>();
  32.         for (int i = 1; i < n; i++) {
  33.             int u = sc.nextInt(), v = sc.nextInt();
  34.             tree[u].add(v);
  35.             tree[v].add(u);
  36.         }
  37.  
  38.         long minCost = Long.MAX_VALUE;
  39.  
  40.         // 枚举每个点作为根节点
  41.         for (int root = 1; root <= n; root++) {
  42.             char target = color[root];
  43.             long cost = dfs(root, -1, target);
  44.             minCost = Math.min(minCost, cost);
  45.         }
  46.  
  47.         System.out.println(minCost);
  48.     }
  49. }
  50.  
Success #stdin #stdout 0.19s 58744KB
comments (?)
stdin
copy 
4
RGBR
3 1 2 4
1 2
2 3
2 4
stdout
copy 
3
https://ideone.com/qKQo9L
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!