Component Tree

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
const int maxx = 3e5 + 4;

int n, par, k, q;
string s;
std::map<string, string> tree[maxx * 4], a[maxx];
int index[maxx];
std::vector<int> g[maxx];

void upd(int x, int y, string key, string value, int id = 1, int l = 0, int r = n){
    if(x >= r or y <= l) return;
    if(x <= l and r <= y){
        if(tree[id][key] == "")
            tree[id][key] = value;
        return;
    }
    int mid = (l + r) / 2;
    upd(x, min(mid, y), key, value, id * 2, l, mid);
    upd(max(mid, x), y, key, value, id * 2 + 1, mid, r);
}

string query(int pos, string key, int id = 1, int l = 0, int r = n){
    if(r - l < 2){
        if(tree[id][key] != "")
            return tree[id][key];
        else
            return "N/A";
    }
    int mid = (l + r) / 2;
    string s1 = "", s2 = "";
    if(pos < mid)
        s1 = query(pos, key, id * 2, l, mid);
    else
        s2 = query(pos, key, id * 2 + 1, mid, r);
    if(s1 == "N/A" or s2 == "N/A"){
        if(tree[id][key] != "")
            return tree[id][key];
        else
            return "N/A";
    }
    return s1 + s2;
}

int dfs(int x, int par, int cnt){
    index[x] = cnt;
    for(auto i: g[x]){
        if(i != par)
            cnt = dfs(i, x, cnt + 1);
    }
    for(auto i: a[x]){
        upd(index[x], cnt + 1, i.F, i.S);
    }
    return cnt;
}

int main(){
    cin>>n;
    for (int i = 1; i <= n; ++i)
    {
        cin>>par>>k;
        g[i].push_back(par);
        g[par].push_back(i);
        for(int j = 0; j < k; j++){
            cin>>s;
            int pos = s.find("=");
            string key = s.substr(0, pos);
            string value = s.substr(pos+1, string::npos);
            a[i][key] = value;
        }
    }
    dfs(1, 0, 0);
    cin>>q;
    int c;
    string name;
    for (int i = 0; i < q; ++i)
    {
        cin>>c>>name;
        cout<<query(index[c], name)<<endl;
        fflush(stdout);
    }
}