結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2019-07-27 02:56:25 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 221 ms / 2,000 ms |
コード長 | 1,485 bytes |
コンパイル時間 | 605 ms |
コンパイル使用メモリ | 74,068 KB |
実行使用メモリ | 27,844 KB |
最終ジャッジ日時 | 2024-10-14 02:00:00 |
合計ジャッジ時間 | 2,897 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
//https://yukicoder.me/problems/no/778#include <iostream>#include <string>#include <vector>#include <deque>#include <queue>#include <algorithm>#include <bitset>#include <tuple>#include <set>#include <map>#define range(i, r) for(int i=0;i<r;i++)#define ranges(i, l, r) for(int i=l;i<r;i++)#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))#define vvi std::vector<std::vector<int> >#define vvl std::vector<std::vector<ll> >#define MODs 1000000007;#define MODn 1000000009;typedef long long int ll;using namespace std;ll ans=0;int M=1;vvi num = vv(300000,0,0,int);std::vector<int> bit;void init(int N){while(M<N) M*=2;M= M*2-1;for(int i=0;i<M;i++) bit.push_back(0);}void add(int a, int k){k += (M+1)/2-1;bit[k]+=a;while(k>0){k=(k-1)/2;bit[k]=bit[k*2+1]+bit[k*2+2];}}int query(int a, int b, int l, int r, int k){if(r<=a||b<=l) return 0;if(a<=l && r<=b) return bit[k];int A = query(a, b, l, (l+r)/2, k*2+1);int B = query(a, b, (l+r)/2, r, k*2+2);return A+B;}void dfs(int cu, int pa=-1){//std::cout << cu << '\n';ans += query(0, cu+1, 0, (M+1)/2, 0);add(1, cu);for(int i=0;i<num[cu].size();i++) if(num[cu][i]!=pa) dfs(num[cu][i], cu);add(-1, cu);}int main(int argc, char const *argv[]) {int N;std::cin >> N;init(N);for(int i=1;i<N;i++){int a;std::cin >> a;num[i].push_back(a);num[a].push_back(i);}dfs(0);std::cout << ans << '\n';return 0;}