Untitled

//---------------
#include<unordered_map>
#include<set>
 
using namespace std;
 
struct node{
    int quantity;
    int priQuantity;
    int parent;
    int numChild;
    int dep; //do sau cua cay
    int kc; //distance tu node --> parent node
    set<int> child;
}Node[10001];
 
int idX;
//unordered_map<int, int> anhxa;
 
//---------------------
void updateParent(int idP, int mQuantity){
    Node[idP].quantity += mQuantity;
 
    while(Node[idP].parent != -1){
        idP = Node[idP].parent;
        Node[idP].quantity += mQuantity;
    }
 
}
 
void init(int N, int mParent[], int mDistance[], int mQuantity[]){
    //clear
    idX = 0;
    //anhxa.clear();
 
    //add root
    Node[idX].child.clear();
    int i = 0;
    Node[idX].parent = -1;
    Node[idX].quantity = mQuantity[i];
    Node[idX].kc = -1;
    Node[idX].numChild = 0;
    Node[idX].dep = 0;
    Node[idX].priQuantity = mQuantity[i];
    idX++;
 
    //add node
    for(i = 1; i < N; i++){
        //add node
        int mP = mParent[i];
        Node[idX].child.clear();
        Node[idX].numChild = 0;
        Node[idX].parent = mP;
        Node[idX].quantity = mQuantity[i];
        Node[idX].kc = mDistance[i];
        Node[idX].dep = Node[mP].dep + 1;
        Node[idX].priQuantity = mQuantity[i];
 
        //update parent
        Node[mP].numChild++;
        Node[mP].child.insert(idX);
        updateParent(Node[idX].parent, mQuantity[i]);
 
        idX++;
    }
}
 
int carry(int mFrom, int mTo, int mQuantity){
    int result = 0;
    Node[mFrom].priQuantity -= mQuantity;
    Node[mTo].priQuantity += mQuantity;
 
    while(Node[mFrom].dep > Node[mTo].dep){
        Node[mFrom].quantity -= mQuantity;
        result += Node[mFrom].kc;
        mFrom = Node[mFrom].parent;
    }
 
    while(Node[mFrom].dep < Node[mTo].dep){
        Node[mTo].quantity += mQuantity;
        result += Node[mTo].kc;
        mTo = Node[mTo].parent;
    }
 
    // khi mFrom.dep == mTo.dep
    while(mFrom != mTo){
        Node[mFrom].quantity -= mQuantity;
        Node[mTo].quantity += mQuantity;
        result += Node[mFrom].kc + Node[mTo].kc; 
 
        mFrom = Node[mFrom].parent;
        mTo = Node[mTo].parent;
    }
 
    return result * mQuantity;
}
 
//------------------------
struct node1{
    int kc;
}dij[10001];
 
 
struct cmp{
    bool operator () (int id1, int id2){
        if(dij[id1].kc == dij[id2].kc){
            return id1 < id2;
        }
        return dij[id1].kc < dij[id2].kc;
    }
};
 
set<int, cmp> hangdoi;
unordered_map<int, int> visit;
int IDDich;
 
int Dijecktra(int mQuantity){
    int cost=0;
     
    int idC = *hangdoi.begin();
    hangdoi.erase(hangdoi.begin());
    visit[idC] = 1;
    //Duyet qua tat ca cac child
    for(auto i = Node[idC].child.begin(); i != Node[idC].child.end(); i++){
        if(!visit[*i]){
            dij[*i].kc = dij[idC].kc + Node[*i].kc;
            hangdoi.insert(*i);
        }
    }
    //Duyet cha cua no
    if(idC != 0){
        int idP = Node[idC].parent;
            if(!visit[idP]){
                dij[idP].kc = dij[idC].kc + Node[idC].kc;
                hangdoi.insert(idP);
            }
        }
     
    while(mQuantity){
        //Push node dau hang doi
        int id = *hangdoi.begin();
        //Delete o dau tien cua hang doi
        hangdoi.erase(hangdoi.begin());
        //Danh dau la da tham
        visit[id] = 1;
 
         
        int numQuantity = mQuantity < Node[id].priQuantity ? mQuantity : Node[id].priQuantity;
        mQuantity -= numQuantity;
        cost += dij[id].kc * numQuantity;
 
        carry(id, IDDich, numQuantity);
        //Duyet qua tat ca cac child
        for(auto i = Node[id].child.begin(); i != Node[id].child.end(); i++){
            if(!visit[*i]){
                dij[*i].kc = dij[id].kc + Node[*i].kc;
                hangdoi.insert(*i);
            }
        }
        //Duyet cha cua no
        if(id != 0){
            int idP = Node[id].parent;
            if(!visit[idP]){
                dij[idP].kc = dij[id].kc + Node[id].kc;
                hangdoi.insert(idP);
            }
        }
    }
 
    return cost;
}
 
int gather(int mID, int mQuantity){
    visit.clear();
    hangdoi.clear();
    IDDich = mID;
 
    //new node
    dij[mID].kc = 0;
    hangdoi.insert(mID);    
 
    return Dijecktra(mQuantity);
}
 
int sum(int mID){
    return Node[mID].quantity;
}