λ¬Έμ
22856λ²: νΈλ¦¬ μν
λ Έλκ° $N$κ°μΈ μ΄μ§ νΈλ¦¬κ° μλ€. νΈλ¦¬λ₯Ό μ€μ μνμ μ μ¬νκ² μννλ €κ³ νλ€. μ΄λ₯Ό μ μ¬ μ€μ μνλΌκ³ νμ. μνμ μμμ νΈλ¦¬μ 루νΈμ΄κ³ μνμ λμ μ€μ μνν λ λ§μ§λ§ λ Έλμ΄λ€.
www.acmicpc.net
νμ΄
1οΈβ£ νΈλ¦¬ ν΄λμ€λ₯Ό μ μν νμ΄
π‘ λ μ€λ₯Έ Idea
μ²μμλ μ΄ λ¬Έμ μμ μ μν μ μ¬ μ€μ μνλ₯Ό λκ°μ΄ ꡬνν΄μΌνλ κ³ λ―Όνμμ§λ§, κ·Έλ¬μ§ μκ³ μ½κ² ν΄κ²°ν μ μμλ€.
μ΄ μ μ¬ μ€μ μνμ νΉμ§μ νΈλ¦¬μμ μ μΌ μ€λ₯Έμͺ½ κ°μ μ νλ²λ§ μ§λκ°κ² λλ€λ νΉμ§μ΄ μλ€.
λ°λΌμ, κ°μ₯ μ€λ₯Έμͺ½ μμλ§ μ§λκ°κ²λ νλ μνλ₯Ό μ μνμ¬ λ Έλμ κ°μλ₯Ό ꡬνκ³
κ°μ μ κ°μλ λ Έλμ κ°μ -1 μμ μ΄μ©νμ¬ νΈλ κ°μ μ κ°μλ₯Ό ꡬν μ μμλ€.
κ·Έλ¦¬κ³ (μ 체 λ Έλμ κ°μ -1)*2 ν κ°μ μ 체 κ°μ μ μ볡 κ°μ μΌλ‘ κ°μ£Όνμλ κ°μμ΄λ―λ‘
μ 체 κ°μ μ μ볡μΌλ‘ μκ°ν κ°μμ νΈλ κ°μ μ κ°μλ₯Ό μ°¨κ°ν΄μ£Όλ©΄ λ΅μ΄ λμ¨λ€.
public class Main {
static int oneWay;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
TreeNode[] nodes = new TreeNode[N + 1];
for (int i = 0; i < N; i++) {
String[] input = br.readLine().split(" ");
int parent = Integer.parseInt(input[0]);
int left = Integer.parseInt(input[1]);
TreeNode leftNode = getNode(nodes, left);
int right = Integer.parseInt(input[2]);
TreeNode rightNode = getNode(nodes, right);
TreeNode parentNode = getNode(nodes, parent);
parentNode.left = leftNode;
parentNode.right = rightNode;
}
order(nodes[1]);
System.out.println((N - 1) * 2 - (oneWay - 1));
}
private static void order(TreeNode node) {
if (node == null) {
return;
}
oneWay++;
order(node.right);
}
private static TreeNode getNode(TreeNode[] nodes, int idx) {
TreeNode node;
if (idx == -1) {
return null;
}
if (nodes[idx] == null) {
node = new TreeNode(idx);
nodes[idx] = node;
} else {
node = nodes[idx];
}
return node;
}
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
}