結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2020-06-11 17:38:08 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 190 ms / 2,000 ms |
コード長 | 1,786 bytes |
コンパイル時間 | 2,037 ms |
コンパイル使用メモリ | 165,484 KB |
実行使用メモリ | 30,624 KB |
最終ジャッジ日時 | 2024-06-24 03:04:15 |
合計ジャッジ時間 | 4,537 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2020.06.11 17:38:04**/#include "bits/stdc++.h"using namespace std;typedef long long ll;template< typename T >struct BinaryIndexedTree {std::vector< T > data;BinaryIndexedTree() {}BinaryIndexedTree(int sz) {data.assign(++sz, 0);}inline T sum(int k) {T ret = 0;for (++k; k > 0; k -= k & -k) ret += data[k];return (ret);}inline T sum(int left, int right) {return sum(right) - sum(left - 1);}inline void add(int k, T x) {for (++k; k < data.size(); k += k & -k) data[k] += x;}int get(ll k) {++k;int res = 0;int N = 1; while (N < (int)data.size()) N *= 2;for (int i = N / 2; i > 0; i /= 2) {if (res + i < (int)data.size() && data[res + i] < k) {k = k - data[res + i];res = res + i;}}return res + 1;}void print() {std::cout << "[ ";for (int i = 0; i < data.size() - 1; i++) {std::cout << sum(i, i);if (i < data.size() - 2) cout << ", ";}std::cout << " ]" << endl;}};vector<vector<int>> g;ll ans;BinaryIndexedTree<int> bit;int n;void dfs(int v, int p = -1) {ll tmp = bit.sum(v+1,n-1);bit.add(v,1);for(int u : g[v]) {if (p == u) continue;dfs(u,v);}ans += bit.sum(v+1,n-1) - tmp;}int main() {cin >> n;g.resize(n);bit = BinaryIndexedTree<int>(n);for (int i = 0; i < n-1; i++) {int a;cin >> a;g[a].push_back(i+1);g[i+1].push_back(a);}dfs(0);cout << ans << endl;return 0;}