結果

問題 No.778 クリスマスツリー
ユーザー tenten
提出日時 2021-01-28 16:29:09
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,406 ms / 2,000 ms
コード長 1,569 bytes
コンパイル時間 2,465 ms
コンパイル使用メモリ 83,028 KB
実行使用メモリ 134,696 KB
最終ジャッジ日時 2024-06-26 00:36:34
合計ジャッジ時間 14,873 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.*;
public class Main {
static BinaryIndexedTree bit;
static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 1; i < n; i++) {
graph.get(sc.nextInt()).add(i);
}
bit = new BinaryIndexedTree(n + 1);
System.out.println(search(0));
}
static long search(int idx) {
long sum = bit.getSum(idx + 1);
bit.add(idx + 1, 1);
for (int x : graph.get(idx)) {
sum += search(x);
}
bit.add(idx + 1, -1);
return sum;
}
}
class BinaryIndexedTree {
int size;
int[] tree;
public BinaryIndexedTree(int size) {
this.size = size;
tree = new int[size];
}
public void add(int idx, int value) {
int mask = 1;
while (idx < size) {
if ((idx & mask) != 0) {
tree[idx] += value;
idx += mask;
}
mask <<= 1;
}
}
public int getSum(int from, int to) {
return getSum(to) - getSum(from - 1);
}
public int getSum(int x) {
int mask = 1;
int ans = 0;
while (x > 0) {
if ((x & mask) != 0) {
ans += tree[x];
x -= mask;
}
mask <<= 1;
}
return ans;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0