結果
問題 | No.778 クリスマスツリー |
ユーザー |
|
提出日時 | 2019-01-01 22:07:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 913 bytes |
コンパイル時間 | 1,507 ms |
コンパイル使用メモリ | 173,440 KB |
実行使用メモリ | 31,432 KB |
最終ジャッジ日時 | 2024-10-14 01:54:58 |
合計ジャッジ時間 | 3,117 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;// one-based numberingtemplate<class T> struct Fenwick {vector<T> bit; int N;Fenwick(int n) {N = n;bit.resize(n+1, 0);}void add(int a, T w) {for (int x = a; x <= N; x += x & -x) bit[x] += w;}T sum(int a) {T ret = 0;for (int x = a; x > 0; x -= x & -x) ret += bit[x];return ret;}};long long dfs(int now, Fenwick<long long> &f, vector<int> v[]) {long long ret = 0;ret += f.sum(now+1); f.add(now+1, 1);for (int i = 0; i < (int) v[now].size(); i++) {ret += dfs(v[now][i], f, v);}f.add(now+1, -1);return ret;}int main() {int n; cin >> n;vector<int> v[n];for (int i = 1; i < n; i++) {int k; cin >> k;v[k].push_back(i);}Fenwick<long long> fenwick(n+1);cout << dfs(0, fenwick, v) << endl;return 0;}