結果
問題 | No.778 クリスマスツリー |
ユーザー |
|
提出日時 | 2020-11-16 13:28:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 806 bytes |
コンパイル時間 | 2,182 ms |
コンパイル使用メモリ | 197,932 KB |
最終ジャッジ日時 | 2025-01-16 01:07:17 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<typename T>struct Ftree {vector<T> dat;Ftree(int n) : dat(n + 1) {}void add(int x, T v) { for (int i = x + 1; i < dat.size(); i += i & -i) dat[i] += v; }T sum(int x) {T r = 0;for (int i = x + 1; i; i -= i & -i) r += dat[i];return r;}};int main() {ios::sync_with_stdio(false);int N; {cin >> N;}vector<vector<int>> G(N); {for (int i = 1; i < N; ++i) {int A; { cin >> A; }G[A].push_back(i);}}int64_t res = 0; {Ftree<int> ftree(N);function<void(int, int)> dfs = [&](int u, int fa) {res += ftree.sum(u);ftree.add(u, +1);for (int v : G[u]) if (v != fa) dfs(v, u);ftree.add(u, -1);};dfs(0, -1);}cout << res << endl;}