Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define INPUT ""
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef unsigned long long ull;
- const ll MAXN = 1234567;
- const ld EPS = 1e-6;
- const ll INF = 1e9;
- ll MOD = 1e9 + 13LL;
- const ll chars = 28;
- ll BASE = 31;
- void pre();
- void post();
- ll n, m;
- struct node
- {
- int next[chars];
- int go[chars];
- int link;
- int pred_v;
- char pred_c;
- bool leaf;
- ll ans;
- ll myans;
- node()
- {
- for(int i=0;i<chars;i++) next[i] = go[i] = -1;
- link = -1;
- pred_v = -1;
- ans = 0;
- myans = 0;
- pred_c = '\0';
- leaf = false;
- ans = 0;
- }
- };
- vector<node> bor;
- vector<node> karas;
- ll link(vector<node> &mas, ll v);
- ll go(vector<node> &mas, ll v, char c)
- {
- if (mas[v].go[c-'a'] != -1)
- return mas[v].go[c-'a'];
- if (mas[v].next[c-'a'] != -1)
- return mas[v].go[c-'a'] = mas[v].next[c-'a'];
- if (mas[v].pred_v == v)
- return mas[v].go[c-'a'] = 0LL;
- return mas[v].go[c-'a'] = go(mas, link(mas, v), c);
- }
- ll link(vector<node> &mas, ll v)
- {
- if (mas[v].link != -1)
- return mas[v].link;
- if (mas[mas[v].pred_v].pred_v == mas[v].pred_v)
- return mas[v].link = 0LL;
- return mas[v].link = go(mas, link(mas, mas[v].pred_v), mas[v].pred_c);
- }
- ll addstring(vector<node> &mas, string &s)
- {
- ll cur = 0;
- for (auto i = s.begin(); i != s.end(); i++)
- {
- if (mas[cur].next[*i-'a'] == -1)
- {
- mas[cur].next[*i-'a'] = mas.size();
- mas.push_back(node());
- mas[mas[cur].next[*i-'a']].pred_v = cur;
- mas[mas[cur].next[*i-'a']].pred_c = *i;
- cur = mas.size() - 1;
- }
- else
- {
- cur = mas[cur].next[*i-'a'];
- }
- }
- mas[cur].leaf = true;
- return cur;
- }
- ll dfs1(ll curbor)
- {
- ll ans=0;
- for(int i=0;i<chars;i++)
- {
- if(bor[curbor].next[i]!=-1)
- ans += dfs1(bor[curbor].next[i]);
- }
- bor[curbor].myans+=ans;
- return bor[curbor].myans;
- }
- void dfs(ll curbor, ll curkaras)
- {
- karas[curkaras].myans += bor[curbor].myans;
- for(int i=0;i<chars;i++)
- {
- if(bor[curbor].next[i]!=-1)
- dfs(bor[curbor].next[i], go(karas, curkaras, i+'a'));
- }
- return;
- }
- bool used[1000099];
- void dfs2(ll cur)
- {
- for(int i=0;i<chars;i++)
- {
- if(karas[cur].next[i]!=-1)
- dfs2(karas[cur].next[i]);
- }
- if (!used[cur] && karas[cur].myans > 0)
- {
- used[cur]=true;
- ll add=karas[cur].myans;
- ll now = link(karas, cur);
- while (karas[now].pred_v != now)
- {
- karas[now].ans += add;
- if(!used[now] && karas[now].myans!=0)
- {
- used[now]=true;
- add+=karas[now].myans;
- }
- now = link(karas, now);
- }
- }
- }
- int main(int argv, char **argc)
- {
- pre();
- cin.sync_with_stdio(false);
- cin >> n;
- bor.resize(1000099);
- karas.resize(1);
- karas.reserve(1000099);
- karas[0].pred_v=0;
- for (int i = 1; i <= n; i++)
- {
- ll p, t;
- char c;
- cin >> p >> c >> t;
- bor[p].next[c-'a'] = i;
- bor[i].pred_c = c;
- bor[i].pred_v = p;
- bor[i].leaf = (t == 1);
- bor[i].myans = (t==1);
- }
- cin >> m;
- pair<string, ll> *strs = new pair<string, ll>[m + 5];
- for (int i = 0; i < m; i++)
- {
- cin >> strs[i].first;
- strs[i].second = addstring(karas, strs[i].first);
- }
- dfs1(0);
- dfs(0, 0);
- dfs2(0);
- for (int i = 0; i < m; i++)
- {
- cout << karas[strs[i].second].myans + karas[strs[i].second].ans << endl;
- }
- post();
- return 0;
- }
- void pre()
- {
- #ifdef DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- if (strcmp(INPUT, "") != 0)
- {
- freopen(INPUT ".in", "r", stdin);
- freopen(INPUT "out", "w", stdout);
- }
- #endif
- }
- void post()
- {
- #ifdef DEBUG
- fprintf(stderr, "Execution time: %Lf", (long double) clock() / CLOCKS_PER_SEC);
- #endif
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement