tries

class trienode{
    public:
    int sum;
    vector<trienode*>children;
    trienode():sum(0),children(26){}
    trienode(int val):sum(val),children(26){}
    ~trienode(){
        for(int i=0;i<26;i++){
            if(children[i]) delete children[i];
            children[i]=nullptr;
        }
        
    }
};
class trie{
    public:
    trienode* node=new trienode();
    void insert(string key,int val,int del){
        trienode* root=node;
        int len=key.size();
        for(int i=0;i<len;i++){
            if(root->children[key[i]-'a']==nullptr){
                root->children[key[i]-'a']=new trienode(val);
            }
            root->sum+=val-del;
            root=root->children[key[i]-'a'];
        }
    }
    int sum(string prefix){
        int len=prefix.size();
        trienode* root=node;
        for(int i=0;i<len;i++){
            if(root->children[prefix[i]-'a']==nullptr){
                return 0;
            }
            root=root->children[prefix[i]-'a'];
        }
        return root->sum;
    }
    
};



class MapSum {
public:
    /** Initialize your data structure here. */
    MapSum() {
        root=new trie();
    }
    unordered_map<string,int>seen;
    void insert(string key, int val) {
        if(seen.count(key)){
            root->insert(key,val,seen[key]);
        }
        else{
            seen[key]=val;
            root->insert(key,val,0);
        }
    }
    
    int sum(string prefix) {
        return root->sum(prefix);
    }
    private:
    trie* root;
};