結果
問題 |
No.778 クリスマスツリー
|
ユーザー |
|
提出日時 | 2025-09-04 17:42:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 215 ms / 2,000 ms |
コード長 | 897 bytes |
コンパイル時間 | 4,082 ms |
コンパイル使用メモリ | 285,216 KB |
実行使用メモリ | 37,868 KB |
最終ジャッジ日時 | 2025-09-04 17:42:13 |
合計ジャッジ時間 | 6,290 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i = 0; i< (n); ++i) #define repi(i, a, b) for (int i = (a); i < (b); ++i) #define all(x) (x).begin(), (x).end() #define fore(i, a) for(auto &i:a) using ll = long long; #include<atcoder/segtree> using namespace atcoder; struct S{ ll value; }; S op(S a, S b){ return S{a.value+b.value}; } S e(){ return S{0}; } int main() { ll n; cin >> n; segtree<S, op, e> seg(2*n); vector<vector<ll>> ch(n); ll a; rep(i, n-1){ cin >> a; ch[a].push_back(i+1); } vector<ll> pre(n), post(n); ll cnt = 0; function<void(ll)> dfs = [&](ll x){ pre[x] = cnt; cnt++; fore(i, ch[x]){ dfs(i); } post[x] = cnt; cnt++; }; dfs(0); ll ans = 0; for(ll i=n-1;i>=0;i--){ ans += seg.prod(pre[i], post[i]+1).value; seg.set(pre[i], {1}); } cout << ans << endl; }