C++ APCS實作題 2020/1 4 : 貨物分配

關於樹狀圖的應用

#include<bits/stdc++.h>
using namespace std;

int w[2000010]={0},st[10010],child[2000010][2],n,m;

int dfs(int a){
    if(a>=n) return w[a];
    w[a]=dfs(child[a][0])+dfs(child[a][1]);
    return w[a];
}

int findBox(int stw,int a){
    if(a>=n){
        return a;
    }
    if(w[child[a][0]]<=w[child[a][1]]){
        w[child[a][0]]+=stw;
        return findBox(stw,child[a][0]);
    }
    w[child[a][1]]+=stw;
    return findBox(stw,child[a][1]);
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);

    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>w[n+i];

    for(int i=0;i<m;i++) cin>>st[i];

    for(int i=1;i<n;i++){
        int p,s,t;cin>>p>>s>>t;
        child[p][0]=s;child[p][1]=t;
    }
    int root=1;
    w[1]=dfs(root);
    for(int i=0;i<m;i++){
        cout<<findBox(st[i],root)<<" ";
    } 

    return 0;
}