#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
using namespace std;
struct Node
{
int id;
int par;
vector<int>child;
int dis;
int level;
int dsum;
int quantity;
}pool[10009];
int poolsize;
void init(int N, int mParent[], int mDistance[], int mQuantity[])
{
poolsize = N;
pool[0].id = 0;
pool[0].par = -1;
pool[0].dis = -1;
pool[0].quantity = mQuantity[0];
pool[0].child.clear();
pool[0].level = 1;
pool[0].dsum = mQuantity[0];
for (int i = 1; i < poolsize; i++)
{
pool[i].id = i;
pool[i].par = mParent[i];
pool[mParent[i]].child.push_back(i);
pool[i].dis = mDistance[i];
pool[i].quantity = mQuantity[i];
pool[i].child.clear();
pool[i].dsum = mQuantity[i];
pool[i].level = pool[mParent[i]].level + 1;
int parentId = mParent[i];
while (parentId != -1)
{
pool[parentId].dsum += mQuantity[i];
parentId = pool[parentId].par;
}
}
}
int carry(int mFrom, int mTo, int mQuantity)
{
int start = pool[mFrom].id;
int end = pool[mTo].id;
pool[start].quantity -= mQuantity;
pool[end].quantity += mQuantity;
int cost = 0;
while (start != end)
{
if (pool[start].level > pool[end].level)
{
pool[start].dsum -= mQuantity;
cost += pool[start].dis;
start = pool[start].par;
}
else if (pool[start].level < pool[end].level) {
pool[end].dsum += mQuantity;
cost += pool[end].dis;
end = pool[end].par;
}
else {
pool[start].dsum -= mQuantity;
cost += pool[start].dis;
start = pool[start].par;
pool[end].dsum += mQuantity;
cost += pool[end].dis;
end= pool[end].par;
}
}
return cost* mQuantity;
}
int gather(int mID, int mQuantity)
{
int cost = 0;
int vis[10009];
int quant = mQuantity;
memset(vis, 0, sizeof(vis));
pool[mID].quantity += mQuantity;
vis[mID] = 1;
vector<pair<int, int>> pendingUpdate;
//pair distance and id
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i = 0; i < pool[mID].child.size(); i++) {
int childId = pool[mID].child[i];
int distance = pool[childId].dis;
pq.push({ distance, childId });
vis[childId] = 1;
}
if (pool[mID].par != -1) {
pq.push({ pool[mID].dis, pool[mID].par });
vis[pool[mID].par] = 1;
}
while (pq.empty() == false) {
auto x = pq.top();
pq.pop();
int currentQuantity = pool[x.second].quantity;
int currentDistance = x.first;
int currentId = x.second;
if (currentQuantity < mQuantity) {
pool[currentId].quantity = 0;
mQuantity -= currentQuantity;
cost += currentQuantity * currentDistance;
pendingUpdate.push_back({ currentId, -currentQuantity });
for (int i = 0; i < pool[currentId].child.size(); i++) {
int childId = pool[currentId].child[i];
if (vis[childId] == 0) {
vis[childId] = 1;
pq.push({ currentDistance + pool[childId].dis, childId });
}
}
int parentId = pool[currentId].par;
if (parentId != -1 && vis[parentId] == 0) {
vis[parentId] = 1;
pq.push({ currentDistance + pool[currentId].dis, parentId });
}
}
else {
pool[currentId].quantity -= mQuantity;
pendingUpdate.push_back({ currentId, -mQuantity });
cost += mQuantity * currentDistance;
break;
}
}
pendingUpdate.push_back({ mID, quant });
for (int i = 0; i < pendingUpdate.size(); i++) {
int currentId = pendingUpdate[i].first;
int distanceToBeModified = pendingUpdate[i].second;
while (currentId != -1) {
pool[currentId].dsum += distanceToBeModified;
currentId = pool[currentId].par;
}
}
return cost;
}
int sum(int mID)
{
return pool[mID].dsum;;
}