Tree Again

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Misha likes playing DotA and he would do nothing else but play it if he could. Unfortunately for Misha, real life is rough and he has to solve following problem before spending a day playing.
You are given a rooted tree with N vertices. Vertices are numerated from 1 to N and vertex 1 is the root of the tree. A positive integer W_{i} is assigned to every node. Consider following code:
Integer sum := 0;
Array of boolean marked := {false, false, false, ..., false};
Procedure Dfs(Integer v)
Begin
sum := sum + W_{v};
marked[sum] := true;
For each node u that v is a parent of u do
Begin
Dfs(u);
End;
End;
One can notice that the state of marked[] array depends on the order vertices u processed. You are to check for every integer number s from 1 to the sum of W_{i} whether there exists some order of viewing children in Dfs that marked[s] = true. Note that marked[] and sum are global variables and Dfs(1) is initially called.
Input
The first line contains integer N — the number of vertices in given tree. N integers W_{i} follow in the next line. Then N1 lines follow, i^{th} of them contains a parent of vertex i+1.
Output
Let S be the sum over all W_{i}. You should output S characters i_{th} of which should be equal to 1 if it is possible to get marked[i] = true and 0 otherwise. Have a look at the example for better understanding.
Constraints
 1 ≤ N ≤ 500
 1 ≤ sum of all W_{i} ≤ 100000
 1 ≤ W_{i} ≤ 100000
 If u is the parent of vertex v then u < v
Example
Input: 5 1 7 7 2 4 1 1 2 4 Output: 100000010100011010001
Author:  rubanenko 
Tester:  shiplu 
Editorial  http://discuss.codechef.com/problems/RRTREE2 
Tags  Rubanenko, cook48, dfs, knapsack, mediumhard 
Date Added:  12072014 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, 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, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 