문제 설명

문제 분석

슈도코드

구현

public class 칵테일_만들기_1033 {
    static ArrayList<CNode>[] arr;
    static long lcm;
    static boolean visited[];
    static long D[];

    public static void main(String[] args) {
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(); // 재료 개수
        arr = new ArrayList[N];
        visited = new boolean[N];
        D = new long[N];
        lcm = 1;
        for (int i = 0; i < N; i++) {
            arr[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int p = scan.nextInt();
            int q = scan.nextInt();
            arr[a].add(new CNode(b, p, q));
            arr[b].add(new CNode(a, q, p));
            lcm *= (p * q / gcd(p, q)); // 최소 공배수는 두 수의 곱을 최대 공약수로 나눈 것
        }
        D[0] = lcm;
        DFS(0);
        long mgcd = D[0];
        for (int i = 1; i < N; i++) {
            mgcd = gcd(mgcd, D[i]);
        }
        for (int i = 0; i < N; i++) {
            System.out.println(D[i] / mgcd + " ");
        }
    }

    // 최대 공약수
    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    // DFS
    public static void DFS(int node) {
        visited[node] = true;
        for (CNode n : arr[node]) {
            int next = n.getB();
            if (!visited[next]) {
                D[next] = D[node] * n.getQ() / n.getP(); // 주어진 비율로 다음 노드값 갱신
                DFS(next);
            }
        }
    }
}

class CNode {
    int b;
    int p;
    int q;

    public CNode(int b, int p, int q) {
        this.b = b;
        this.p = p;
        this.q = q;
    }

    public int getB() {
        return b;
    }

    public int getP() {
        return p;
    }

    public int getQ() {
        return q;
    }
}