cfgym100513C

（ACM）数据结构----树链剖分 201707

• 树链剖分：一个点到根节点上最多跳log条重链
• 因此把整条链上的信息存在链顶部 map<key, set<tid,val> > [N];
• 查找链上一个点的信息时，二分找tid就行了。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int N=300005;
int n;
int fa[N],siz[N],son[N],top[N],tid[N];
vector<string> vv[N];
vector<int> G[N];
map<string,set<pair<int,string> > > mess[N];
set<pair<int,string> >::iterator it;
void dfs1(int u) {
    siz[u]=1;
    rep(i,0,sz(G[u])) {
        int v=G[u][i];
        dfs1(v);
        siz[u]+=siz[v];
        if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int tp,int d) {
    top[u]=tp;
    tid[u]=d;
    if(son[u]==-1) return ;
    dfs2(son[u],tp,d+1);
    rep(i,0,sz(G[u])) {
        int v=G[u][i];
        if(v!=son[u]) dfs2(v,v,1);
    }
}
int main() {
    ios::sync_with_stdio(false);
    ///
    cin>>n;
    ///init
    memset(son,-1,sizeof(son));
    ///read
    rep(i,1,n+1) {
        int m;cin>>fa[i]>>m;
        G[fa[i]].pb(i);
        rep(j,0,m) {
            string s;cin>>s;
            vv[i].pb(s);
        }
    }
    ///
    dfs1(1);
    dfs2(1,1,1);
    ///solve
    rep(i,1,n+1) {
        rep(j,0,sz(vv[i])) {
            string b=vv[i][j].substr(vv[i][j].find('=')+1);
            vv[i][j].erase(vv[i][j].find('='));
            string a=vv[i][j];
            mess[top[i]][a].insert(mp(tid[i],b));
        }
    }
    int q;cin>>q;
    while(q--) {
        int u;string s;
        cin>>u>>s;
        int f=1;
        while(u>0) {
            it = mess[top[u]][s].upper_bound(mp(tid[u],string("zzzzzzzzzzzzzzz")));
            if(it==mess[top[u]][s].begin()) u=fa[top[u]];
            else {
                --it;
                f=0;
                cout<<it->se<<endl;
                break;
            }
        }
        if(f) cout<<"N/A"<<endl;
        fflush(stdout);
    }
    return 0;
}