Zoom 2023届校园招聘-Java方向0810

最开始想的建树，但是好像有点麻烦，直接用邻接矩阵存储结点关系，然后遍历，结果报堆溢出，想来可能是后面结点数太大了，创建邻接矩阵的时候就导致堆溢出，改为邻接表，用ArrayList来存储结点

遍历获取权重计算

import java.util.*;

public class Main {
    static int[] weights;
    static int[] ans;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String colors = scanner.nextLine();
        weights = new int[n];
        for (int i = 0; i < n; i++)
            weights[i] = colors.charAt(i)=='R' ? 1 : -1;

        List<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++)
            graph.add(new ArrayList<Integer>());

        for (int i = 0; i < n-1; i++) {
            int start = scanner.nextInt(), end = scanner.nextInt();
            graph.get(start-1).add(end-1);
            graph.get(end-1).add(start-1);
        }

        ans = new int[n];
        ans[0] = weights[0];
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        visited[0] = true;
        queue.add(0);
        while(!queue.isEmpty()) {
            int pre = queue.poll();
            for (int i = 1; i < graph.get(pre).size(); i++) {
                int temp = graph.get(pre).get(i);
                if (temp != pre && !visited[temp]) {
                    ans[temp] = weights[temp] + ans[pre];
                    visited[temp] = true;
                    queue.add(temp);
                }
            }
        }

        int sum = 0;
        for (int a : ans)
            sum += Math.abs(a);

        System.out.println(sum);
    }
}