結果

問題 No.778 クリスマスツリー
ユーザー beetbeet
提出日時 2019-01-13 20:46:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 186 ms / 2,000 ms
コード長 2,323 bytes
コンパイル時間 2,286 ms
コンパイル使用メモリ 204,348 KB
実行使用メモリ 28,860 KB
最終ジャッジ日時 2024-04-22 03:06:08
合計ジャッジ時間 4,293 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 128 ms
28,860 KB
testcase_07 AC 70 ms
24,616 KB
testcase_08 AC 186 ms
28,416 KB
testcase_09 AC 160 ms
24,252 KB
testcase_10 AC 154 ms
24,320 KB
testcase_11 AC 160 ms
24,192 KB
testcase_12 AC 148 ms
24,252 KB
testcase_13 AC 99 ms
24,448 KB
testcase_14 AC 120 ms
28,800 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct EulerTour{
  Int n,pos;
  vector<vector<Int> > G;
  vector<Int> ls,rs;
  
  EulerTour(){}
  EulerTour(Int n):n(n),G(n),ls(n),rs(n){}

  void add_edge(Int u,Int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void dfs(Int v,Int p){
    ls[v]=pos++;
    for(Int u:G[v])
      if(u!=p) dfs(u,v);
    rs[v]=pos;
  }
  
  void build(Int r=0){
    pos=0;
    dfs(r,-1);
  }
  
};


template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  Int n;
  F f;
  G g;
  T ti;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(F f,G g,T ti):f(f),g(g),ti(ti){}

  void init(Int n_){    
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }
  void build(const vector<T> &v){
    Int n_=v.size();
    init(n_);
    for(Int i=0;i<n_;i++) dat[n+i]=v[i];
    for(Int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  void update(Int k,E a){
    k+=n;
    dat[k]=g(dat[k],a);
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }
  void set_val(Int k,T x){
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);    
  }
  T query(Int a,Int b){
    T vl=ti,vr=ti;
    for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }
  template<typename C>
  Int find(Int a,Int b,C &check,Int k,Int l,Int r){
    if(!check(dat[k])||r<=a||b<=l) return -1;
    if(k>=n) return k-n;
    Int m=(l+r)>>1;
    Int vl=find(a,b,check,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(a,b,check,(k<<1)|1,m,r);
  }
  template<typename C>
  Int find(Int a,Int b,C &check){
    return find(a,b,check,1,0,n);
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  EulerTour G(n);
  for(Int i=1;i<n;i++){
    Int p;
    cin>>p;
    G.add_edge(p,i);
  }
  G.build();
  auto f=[](Int a,Int b){return a+b;};
  SegmentTree<Int, Int> seg(f,f,0);
  seg.build(vector<Int>(n,0));
  Int ans=0;
  for(Int i=n-1;i>=0;i--){
    ans+=seg.query(G.ls[i],G.rs[i]);
    seg.update(G.ls[i],1);
  }
  cout<<ans<<endl;
  return 0;
}
0