結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2023-04-02 15:40:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 232 ms / 2,000 ms |
コード長 | 1,348 bytes |
コンパイル時間 | 4,278 ms |
コンパイル使用メモリ | 254,664 KB |
最終ジャッジ日時 | 2025-02-11 22:18:17 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;//using mint = static_modint<998244353>;//using mint = modint;using mint = static_modint<1000000007>;using vm = vector<mint>;using vvm = vector<vm>;ostream &operator<<(ostream &o,const mint &m){cout<<m.val();return o;}using ll = long long;using vl = vector<ll>;using vvl = vector<vl>;using pl = pair<ll,ll>;#define rep(i,n) for(ll i=0;i<(ll)(n);++i)#define reps(i,s,n) for(ll i=(s);i<(ll)(n);++i)#define rep1(i,n) for(ll i=1;i<=(ll)(n);++i)#define chmin(x,y) x=min(x,y)#define chmax(x,y) x=max(x,y)const long long INF = 1e18;#ifdef DEBUG#include <debug.hpp>#endifint main(){#ifdef DEBUGcout << "--- Input ---" << endl;#endifll N;cin>>N;vvl g(N);reps(v,1,N){ll u;cin>>u;g.at(u).push_back(v);g.at(v).push_back(u);}fenwick_tree<ll> bit(N);ll ans=0;auto rec=[&](auto f,ll u,ll p=-1)->void{#ifdef DEBUGcout<<"u="<<u<<" p="<<p<<endl;#endifassert(u>=0&&u<N);ans+=bit.sum(0,u);bit.add(u,1);rep(v,g.at(u).size()){if(g.at(u).at(v)==p)continue;f(f,g.at(u).at(v),u);}bit.add(u,-1);};#ifdef DEBUGcout<<g;cout << "--- Logic ---" << endl;#endifrec(rec,0);#ifdef DEBUGcout << "--- Answer ---" << endl;#endifcout<<ans<<endl;return 0;}//cout << fixed << setprecision(9);