SWEA 26390. 트리 바꾸기

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

1<=n<=300000인 n에 대해서 n개의 정점과 n-1개의 간선으로 이루어진 트리를 모든 정점이 최대 2개의 서로 다른 정점과 연결되어 있는 체인으로 만드는데 필요한 작업의 수를 구하는 문제이다. 작업은 이미 연결된 정점 X, Y 를 골라 X와 Y 사이의 간선을 끊고, X에 연결되어 있지 않은 정점 Z를 골라 X와 Z를 연결한다.

 

정점에 대한 간선 정보를 통해 차수를 구한 후, 정점들이 2개까지만 갖게 절단하면 되므로 이 차수가 3개 이상인 정점들의 (차수 - 2)의 합을 구하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
		
        while (tc-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[] degree = new int[n + 1];

            for (int i = 0; i < n - 1; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                degree[u]++;
                degree[v]++;
            }

            long answer = 0;
            for (int i = 1; i <= n; i++) {
                if (degree[i] > 2) {
                    answer += degree[i] - 2;
                }
            }

            sb.append(answer).append('\n');
        }
        br.close();
        System.out.print(sb);
	}
}