Path In The Tree

All submissions for this problem are available.
Problem description.
You are given a string (named str) of length l (consisting of lowercase english alphabets (roman)), and a tree with n number of nodes. Each node of the tree has a character(again lowercase english alphabet) written on it. The tree is ROOTED AT 1. If on the tree, we find a path, such that it is vertical (runs from top to bottom), and starting from the node nearer to the root (say x), we note down the characters on the nodes while traversing the tree to the bottom (upto the node ending the path) (say y), if the string generated exactly matches with the given string, then we place a tick at node y. Let function F(v) be defined as : number of ticked nodes in the subtree of v (obviously that includes v). You have to print the value of F(v) from every node v=1,2,...,n;
NOTE:
 The path to be selected should be vertical, i.e., no two nodes in the path should have the same depth.
 The tree can be heavily branched or skewed.
 Test data is large, hence refrain from using slow input/output techniques.
Input
First line consists of integer T, denoting the number of test cases Next line consists of integers n and l, number of nodes in the tree and the length of the given string str. Next line contains the string. It is assured to be of length l. Next n lines,ith of which will be of format c p where c is the character of the i^{th} node, p is the parent of ith node (since the tree is rooted) It is important to note that parent of node 1 will be given as 0 as it is the root and has no parent.
Output
For each test case output a single line containing n space separated integers ith of which will be the value of F(i). .
Constraints
Subtask 1 : 25 points
 T ≤ 10
 n ≤ 10^3
 Length of string ≤ n
Subtask 2 : 75 points
 T ≤ 10
 n ≤ 10^5
 Length of string ≤ n
Example
Input: 2 10 2 sm s 0 s 1 m 2 s 3 m 4 s 5 m 6 m 7 s 8 m 9 10 1 y y 0 y 1 y 2 y 3 y 4 y 5 y 6 y 7 y 8 y 9 Output: 4 4 4 3 3 2 2 1 1 1 10 9 8 7 6 5 4 3 2 1
Author:  abhi1agarwal 
Tags  abhi1agarwal 
Date Added:  22052017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, PAS fpc, PAS gpc, RUBY, PHP, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, ERL, TCL, PERL6, TEXT, SCM chicken, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions