+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Jeff and Sehri decided to divide Semnan among themselves. for simplicity let's assume Semnan is a tree consisting of $n$ nodes. A tree with $n$ nodes is a undirected connected graph with with $n - 1$ edges. We also define an array $F$ of length $N$ of integers between 1 to 100,000. Amin gives each of Semnan's tree nodes to either Jeff and Sehri, after Amin divides Semnan each of Jeff or Sehri will have a forest, where forest is a disjoint union of trees. if Jeff's forests consists of $k$ connected components and each of them have $c_1$, $c_2$, ..., $c_k$ number of nodes, his happiness is $$\sum_{i=1}^{k} F_{C_i}$$ Sehri's happiness is calculated in the same way. and after that, the amount of happiness of Amin will be the XOR of happiness of Jeff and Sehri. Amin wonders what is the sum of his happiness over all $2^n$ possible divisons of Semnan? Help Amin with this problem. # input the first line of input consists of the number $n$ the number of nodes in Semnan. the next line will be $n - 1$ numbers $p_2$, $p_3$, ..., $p_n$ where $p_i$ is an edge between node number i and $p_i$. then in the next line there are N numbers denoting array F where the i-th number is $F_i$. $$1 \le n \le 26$$ $$1 \le p_i \le i + 1$$ $$1 \le F_i \le 100,000$$ # output output should consist of a single number the sum of Amin's happiness over all possible $2^n$ divisions of Semnan. # example ### sample input 1 ``` 3 1 1 10 5 15 ``` ### sample output 1 ``` 150 ``` + If Jeff gets no nodes Jeff's happiness would be zero but Sehri would get all 3 nodes then Sehri's forest would consist of one component of size 3 then Sehri's happiness would be equal to $F_3=15$ since $15 xor 0 = 15$ Amin's happiness would be equal to 15. + If Jeff gets one node, Jeff's forest would consist of one connected component of size 1 so Jeff's happiness would be equal to $F_1=10$ but if the node Jeff gets is node number 1 Sehri's forest would consist of 2 connected components of size one so Sehri's happiness would be $F_1+F_1=20$ and Amin's happiness would be $10 xor 20 = 30$ but if Jeff gets is the node 2 or 3 Sehri's forest would consist of one connected component of size 2 so Sehri's happiness would be $F_2=5$ and Amin's happiness would be equal to $10 xor 5 = 15$. + If Jeff gets two or three nodes it is similar to the previous cases so we have $15+30+15+15+30+15+15+15=150$ ### sample input 2 ``` 5 1 1 2 2 10 2 15 3 1 ``` ### sample output 2 ``` 566 ```

حل سؤال در بانک سؤالات