GP_of_Udmurtia_2014_I.cpp

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
    ost<<"{"<<p.first<<","<<p.second<<"}";
    return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
    ost<<"{";
    for(int i=0;i<v.size();i++){
        if(i)ost<<",";
        ost<<v[i];
    }
    ost<<"}";
    return ost;
}

struct AhoCorasick{
	struct Node{
		map<char,int>nex;
		int failink;
		int len;
		Node():failink(0),len(0){}
	};
	vector<Node>nds;
	AhoCorasick(){
		nds.emplace_back();
		nds[0].failink=-1;
	}

    /*
	int process(int k,int c){
		while(k!=-1&&nds[k].nex.find(c)==nds[k].nex.end())k=nds[k].failink;
		if(k==-1)return 0;
		return nds[k].nex[c];
	}*/
    int process(int k,char c){
        if(k==-1)return 0;
        if(nds[k].nex.find(c)!=nds[k].nex.end())return nds[k].nex[c];
        return nds[k].nex[c]=process(nds[k].failink,c);
    }

	int add(const string &s){
		int k=0;
		for(auto c:s){
			if(nds[k].nex.find(c)==nds[k].nex.end()){
				nds[k].nex[c]=nds.size();
				nds.emplace_back();
				nds.back().len=nds[k].len+1;
			}
			k=nds[k].nex[c];
		}
        return k;
	}

	void build(){
		queue<int>que;
		for(auto &p:nds[0].nex)que.push(p.second);
		while(que.size()){
			int k=que.front();
			que.pop();
			for(auto &p:nds[k].nex){
				char c=p.first;
				int nx=p.second;
				nds[nx].failink=process(nds[k].failink,c);
				que.push(nx);
			}
		}
	}
};

char buf[1111111];

vector<pair<int,char>>G[1111111];
int cnt[1111111];

void calcCnt(int v){
    for(auto &e:G[v]){
        calcCnt(e.fi);
        cnt[v]+=cnt[e.fi];
    }
}

AhoCorasick ac;
int app[1111111];

void calcApp(int v,int k){
    app[k]+=cnt[v];
    for(auto &e:G[v]){
        calcApp(e.fi,ac.process(k,e.se));
    }
}
signed main(){
    int N;
    scanf("%lld",&N);
    for(int i=1;i<=N;i++){
        int p;
        char c;
        int f;
        scanf("%lld %c%lld",&p,&c,&f);
        G[p].eb(i,c);
        cnt[i]=f;
    }

    calcCnt(0);

    int Q;scanf("%lld",&Q);
    vector<int>id(Q);
    rep(i,Q){
        string s;cin>>s;
        id[i]=ac.add(s);
    }
    ac.build();
    calcApp(0,0);

    vint deg(ac.nds.size());
    rep(i,ac.nds.size())if(ac.nds[i].failink!=-1)deg[ac.nds[i].failink]++;
    queue<int>que;
    rep(i,ac.nds.size())if(deg[i]==0)que.push(i);
    while(que.size()){
        int v=que.front();
        que.pop();
        int p=ac.nds[v].failink;
        if(p==-1)continue;
        app[p]+=app[v];
        if(--deg[p]==0){
            que.push(p);
        }
    }

    rep(i,Q)printf("%lld\n",app[id[i]]);
    return 0;
}