結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2022-04-23 16:12:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 1,020 bytes |
コンパイル時間 | 1,921 ms |
コンパイル使用メモリ | 199,308 KB |
最終ジャッジ日時 | 2025-01-28 21:12:19 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;void dfs(vector<vector<int>> &c, vector<int> &L, vector<int> &R, int &t, int v = 0){L[v] = t;t++;for (int w : c[v]){dfs(c, L, R, t, w);}R[v] = t;}struct binary_indexed_tree{int N;vector<int> BIT;binary_indexed_tree(int N): N(N), BIT(N + 1, 0){}void add(int i){i++;while (i <= N){BIT[i]++;i += i & -i;}}int sum(int i){int ans = 0;while (i > 0){ans += BIT[i];i -= i & -i;}return ans;}int sum(int L, int R){return sum(R) - sum(L);}};int main(){int N;cin >> N;vector<int> A(N, -1);for (int i = 1; i < N; i++){cin >> A[i];}vector<vector<int>> c(N);for (int i = 1; i < N; i++){c[A[i]].push_back(i);}vector<int> L(N), R(N);int t = 0;dfs(c, L, R, t);binary_indexed_tree BIT(N);long long ans = 0;for (int i = N - 1; i >= 0; i--){ans += BIT.sum(L[i], R[i]);BIT.add(L[i]);}cout << ans << endl;}