개발자 톡
연습문제 톡
[21년 재직자 대회 본선] 거리 합 구하기
[재직자 본선 거리합 문제], Algo Tutor에 있는 로직 그대로 java에 옮겼는데 왜 틀릴까요..?
- 등록일
- 2022-01-04 12:47:25
- 조회수
- 1166
- 작성자
- zaza1994
몇가지 테스트 케이스 직접 돌려보고 같은 값이 나오는 거 확인했습니다.
도대체 어느 부분에서 문제가 되는지 알고 싶습니다.
도와주세요
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static int N;
static LinkedList[] nodes;
static int[] ans, subTree, distSum;
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
nodes = new LinkedList[N+1];
ans = new int[N+1];
subTree = new int[N+1];
distSum = new int[N+1];
for(int n = 0; n < N+1; n++) nodes[n] = new LinkedList<>();
for(int n = 0; n < N-1; n++) {
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
nodes[n1].add(new Integer[]{n2,c});
nodes[n2].add(new Integer[]{n1,c});
}
dfs1(1,0);
// for(int n = 0; n < N; n++) System.out.println(distSum[n+1]);
dfs2(1,0);
for(int n = 0; n < N; n++) System.out.println(distSum[n+1]);
}
static void dfs1(int cur, int prv) {
subTree[cur] = 1;
for(Integer[] arr : nodes[cur]) {
int child = arr[0];
int weight = arr[1];
if(child != prv) {
dfs1(child, cur);
distSum[cur] += distSum[child] + subTree[child]*weight;
subTree[cur] += subTree[child];
}
}
}
static void dfs2(int cur, int prv){
for(Integer[] arr : nodes[cur]) {
int child = arr[0];
int weight = arr[1];
if(child != prv) {
distSum[child] = distSum[cur] + weight*(N-2*subTree[child]);
dfs2(child, cur);
}
}
}
}
#[21년_재직자_대회_본선]_거리_합_구하기
#거리합문제
#java