트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)

제한사항
a의 길이는 2 이상 300,000 이하입니다.
a의 모든 수는 각각 -1,000,000 이상 1,000,000 이하입니다.
a[i]는 i번 정점의 가중치를 의미합니다.
edges의 행의 개수는 (a의 길이 - 1)입니다.
edges의 각 행은 [u, v] 2개의 정수로 이루어져 있으며, 이는 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미합니다.
edges가 나타내는 그래프는 항상 트리로 주어집니다.

처음 생각한것

트리이고 부모는 하나일수밖에 없으므로 가장 낮은 노드에서 높은 노드로 값을 옮기면서
가중치를 0으로 만들어야한다.
루트를 찾는법. 가장 낮은 노드는 연결된값이 없으므로 (부모노드만 연결됨) 그것을 통해서 부모노드로 값을 이동.
루트노드가 어디냐는 중요하지않다.

코드

import java.util.*;
class Solution {
    static long answer = 0;
    static long[] tmp;
    static boolean[] visit;
    static List<Integer>[] list;
    public long solution(int[] a, int[][] edges) {
        list = new ArrayList[a.length];
        visit = new boolean[a.length];
        tmp = new long[a.length];
        long sum = 0;
        for(int i=0;i<a.length;i++){
            list[i] =new ArrayList<Integer>();
            tmp[i] = a[i];
            sum+=a[i];
        }        
        if(sum!=0) return -1;
        //인접리스트 생성
        for(int i=0;i<edges.length;i++){
            list[edges[i][0]].add(edges[i][1]);
            list[edges[i][1]].add(edges[i][0]);
        }      
        //dfs를 통한 부모노드로 값 이동
        dfs(0);       
        return answer;
    }
    void graph(int x,int y,ArrayList<ArrayList<Integer>> list){
        list.get(x).add(y);
        list.get(y).add(x);
    }
    long dfs(int node){
        visit[node] = true;
        for(int i=0; i<list[node].size(); i++){
            int next = list[node].get(i);           
            if(visit[next]) continue;
            tmp[node] += dfs(next);            
        }
     
        long num = tmp[node];
        answer += Math.abs(num);
        return num;
    }
}

문제를 풀면서 테스트 케이스 2개가 런타임 오류가 계속 생기는걸 확인할수있었다.
DFS로 풀어서인지 힙사이즈에 대한 압박이 있어서 그랬다. BFS형태로 풀면 런타임 오류는 일어나지않는다.

BFS

import java.util.*;
class Solution {
    static long answer = 0;
    static long[] tmp;
    static boolean[] visit;
    static List<Integer>[] list;
    public long solution(int[] a, int[][] edges) {
        list = new ArrayList[a.length];
        visit = new boolean[a.length];
        tmp = new long[a.length];
        int[] adnode = new int[a.length]; 
        Queue<Integer> q = new LinkedList<>();
        long sum = 0;
        for(int i=0;i<a.length;i++){
            list[i] =new ArrayList<Integer>();
            tmp[i] = a[i];
            sum+=a[i];
        }        
        if(sum!=0) return -1;
        //인접리스트 생성
        for(int i=0;i<edges.length;i++){
            adnode[edges[i][0]]++;
            adnode[edges[i][1]]++;
            list[edges[i][0]].add(edges[i][1]);
            list[edges[i][1]].add(edges[i][0]);
        }      
        //bfs를 통한 부모노드로 값 이동
         for (int i = 0; i < a.length; i++) { 
            if (adnode[i] == 1)
                q.add(i);
        }

        while (!q.isEmpty()) { 
            int node = q.remove();

            visit[node] = true;
            long value = tmp[node];

            for (int i = 0; i < list[node].size(); i++) { 
                int next = list[node].get(i);

                if (!visit[next]) {
                    adnode[next]--;
                    tmp[next] += value;
                    tmp[node] = 0;
                    answer += Math.abs(value);

                    if (adnode[next] == 1) {
                        q.add(list[node].get(i));
                    }

                    break;
                }
            }
        }    
        return answer;
    }
  
}