#include "tree.h" // ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39] // Author: Sazid Hasan #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double dl; typedef vector<int> vi; typedef vector<vector<int>> vii; typedef vector<ll> vl; typedef vector<bool> vb; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second #define all(a) a.begin(), a.end() #define gcd(a, b) __gcd(a, b) #define lcm(a, b) (a * (b / gcd(a, b))) #define spc " " #ifdef ONLINE_JUDGE #define debarr(array) #define deb(x) #define del #else #define debarr(array) \ for (int w = 0; w < array.size(); w++) \ cerr << #array << "-" << w << " = " << array[w] << endl; #define deb(x) cerr << #x << " = " << x << endl; #define del cerr << '\n'; #endif const double PI = acos(-1); const int MOD = 1000000007; const int inf = (2147483647); int n; std::vector<int> p, w; vi cnt; ll leaf = 0; int dfs(vii &adj, int i, vi &W) { if (adj[i].size() == 0) { leaf++; return 1; } int c = 0; for (auto x : adj[i]) { c += dfs(adj, x, W); } if (W[i] == 0) { cnt[c]++; return 1; } else { return c; } } void init(std::vector<int> P, std::vector<int> W) { n = P.size(); cnt.resize(n + 5); vii adj(n + 1); for (int i = 1; i < n; i++) adj[P[i]].push_back(i); cnt[dfs(adj, 0, W)]++; for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1]; } long long query(int L, int R) { ll l = L, r = R; ll cost = (leaf * l) + (max(0LL, (leaf * l))); int k = R/L; k = min(k, n); cost -= cnt[n]*(l); cost += cnt[k]*l + (r*(cnt[n]- (k<1 ? 0 : cnt[k-1]) )); return cost; }