//https://yukicoder.me/problems/no/778 #include #include #include #include #include #include #include #include #include #include #define range(i, r) for(int i=0;i >(a, vector(b, c)) #define vvi std::vector > #define vvl std::vector > #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 bit; void init(int N){ while(M0){ 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> N; init(N); for(int i=1;i> a; num[i].push_back(a); num[a].push_back(i); } dfs(0); std::cout << ans << '\n'; return 0; }