#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2000;
int N;
vector<int> W;
vector<vector<int>> adj;
int tin[MAXN], tout[MAXN], depth[MAXN];
struct Fenwick {
int n;
vector<int> bit;
Fenwick(int n) {
this->n = n;
bit = vector<int>(n + 1);
}
void update(int i, int delta) {
for (i += 1; i <= n; i += i & -i) {
bit[i] += delta;
}
}
int sum(int i) {
int res = 0;
for (i += 1; i > 0; i -= i & -i) {
res += bit[i];
}
return res;
}
int sum(int l, int r) {
return sum(r) - sum(l - 1);
}
void init() {
for (int i = 0; i <= n; ++i) {
bit[i] = 0;
}
}
} tree(MAXN * 2);
void init(std::vector<int> P, std::vector<int> _W) {
N = (int)P.size();
W = _W;
adj.resize(N);
for (int i = 1; i < N; ++i) {
adj[P[i]].push_back(i);
adj[i].push_back(P[i]);
}
vector<vector<int>> nadj(N);
vector<bool> vis(N);
for (int i = 1; i < N; ++i) {
if (vis[i]) continue;
if (adj[i].size() == 2) {
int v1 = adj[i][0];
int v2 = adj[i][1];
int p1 = i;
int p2 = i;
vis[i] = 1;
while (adj[v1].size() == 2 && v1 != 0) {
vis[v1] = 1;
for (auto& u : adj[v1]) {
if (u != p1) {
p1 = v1;
v1 = u;
break;
}
}
}
while (adj[v2].size() == 2 && v2 != 0) {
vis[v2] = 1;
for (auto& u : adj[v2]) {
if (u != p2) {
p1 = v2;
v2 = u;
break;
}
}
}
cerr << "Found new = " << v1 << " " << v2 << "\n";
nadj[v1].push_back(v2);
nadj[v2].push_back(v1);
} else {
for (auto& u : adj[i]) {
if (u != 0 && adj[u].size() == 2) continue;
nadj[u].push_back(i);
nadj[i].push_back(u);
}
}
}
adj = nadj;
for (auto& v : adj) {sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v));}
int t = 1;
cerr << "Size = " << adj.size() << endl;
for (int i = 0; i < N; ++i) {
cerr << i << " : ";
for (auto& u : adj[i]) {
cout << u << " , ";
}
cout << endl;
}
auto dfs = [&](auto& dfs, int v, int p) -> void {
tin[v] = t++;
for (auto& u : adj[v]) {
if (u == p) continue;
cout << "Vertices " << v << " and " << u << " are connected!\n";
depth[u] = depth[v] + 1;
dfs(dfs, u, v);
}
tout[v] = t++;
};
dfs(dfs, 0, -1);
}
long long query(int L, int R) {
// cerr << "QUERY WITH " << L << " " << R << endl;
ll res = 0;
queue<int> q;
vector<vector<int>> leaves(N);
tree.init();
for (int i = 1; i < N; ++i) {
if (adj[i].size() == 1) {
res += 1LL * W[i] * L;
q.push(adj[i][0]);
tree.update(tin[i], +L);
}
}
vector<bool> inq(N);
while (q.size()) {
int v = q.front();
q.pop();
int sum = tree.sum(tin[v], tout[v]);
leaves[v].push_back(v);
sort(begin(leaves[v]), end(leaves[v]), [&](int x, int y) {
return W[x] < W[y];
});
for (int i = 0; i < (int)leaves[v].size() && sum < L; ++i) {
int current = leaves[v][i];
int left = L - sum;
res += left * W[current];
tree.update(tin[current], +left);
sum += left;
}
for (int i = 0; i < (int)leaves[v].size() && sum > R; ++i) {
int current = leaves[v][i];
int left = min(sum - R, max(0, tree.sum(tin[current], tout[current]) - L));
res += left * W[current];
tree.update(tin[current], -left);
sum -= left;
}
for (auto& u : adj[v]) {
if (depth[u] < depth[v]) {
while (leaves[v].size()) {
int current = leaves[v].back();
leaves[v].pop_back();
if (tree.sum(tin[current], tout[current]) == L) continue;
leaves[u].push_back(current);
}
if (!inq[u]) {
q.push(u);
inq[u] = 1;
}
}
}
}
return res;
}
