Assignment 11 Solution

This problem involves simulating a simple model of a "distributed" database.

Consider for example the problem of translating URL's of web sites to actual IP

addresses. One way to do it would be to maintain a map from all web addresses to

corresponding IP addresses in one place. However this would mean that every time

a web site is accessed, this map would have to be accessed. This would put too

much load on one machine and the size of the map would be very large. To reduce

this, the look up task is "distributed" among different machines, that are

arranged in a tree like structure. The root node represents the main map that

stores all addresses. Each node maintains a subset of the addresses, usually

much fewer than the total number. A query is first sent to the "nearest" node 

in the tree. If the answer is found there, it is returned immediately, otherwise 

the query is forwarded to the parent of the node, which uses the same method to 

find the answer, and forwards it to the child that requested it. If the query 

reaches the root, it is answered. When a node gets an answer from its parent, it 

stores it in its local memory so that next time it gets the same query, it can 

answer immediately. This is called caching. To keep the lookup time small, the 

number of addresses that can be stored in a node is limited. A common method used 

to maintain a subset of addresses is to throw out the least recently used address,

if the number of stored addresses exceeds the capacity. This is based on the

assumption that a web site accessed recently would be accessed again, so can be

looked up efficiently.




You have to simulate this process, given the sequence of queries made, the number

of addresses that each node can store, and the tree structure. Assume that

initially, only the root node has the complete map, and all other nodes do not

contain any addresses. Also, each query is processed completely, before the next

query is considered.







Input Format

The first line of input specifies n the number of nodes in the tree and m the

number of queries. Assume 1 <= n <= 1000, and 1 <= m <= 1000000. The next line

contains n-1 numbers, the ith number being the parent of node number i. Node 0 

is the root node. The next line contains n-1 numbers, the ith number is the

capacity of node number i. This is at least 1 and at most m. The root node has

capacity m. The next m lines specify the queries. Each line contains a string

(the query) and a node number giving the node to which the query is first made.

The string has only lower case characters and length at most 32. 




Output Format

Assume that the cost of looking for the answer in a node of capacity c is 1 +

floor of log_2 c. Print out the total cost of all the lookups performed at all

the nodes together for all the queries.




Sample Input

3 4

0 1

2 1

a 2

b 1

c 2

b 2




Sample Output

20




Explanation: The first query is looked up at nodes 2,1 and 0 for a cost of 1+2+3

= 6. The second query is looked up at 1 and 0, for a cost of 2+3 = 5. The third

query is looked up at nodes 2, 1 and 0 with cost 6. After this node 2 contains

the address c, while node 1 contains b and c. Note that b was looked up after 

a at node 1, so a was the least recently used address at node 1, and is replaced

by c. The last query is looked up at nodes 2 and 1, where the answer is found, 

so the cost is 1+2 = 3. The total cost is 14.




Question: Can you find the optimal way of storing addresses in the nodes of the

tree so that the cost of processing a given sequence of queries is minimized? 

In this case, each node stores a fixed subset of addresses of size at most its

capacity. In the sample input, if node 1 stores a and b and node 2 stores c, 

the cost for the sequence is 9.




Note that the actual mapping is not relevent. Each node can store the set of

addresses for which it has the mapping. It may be faster to use hashing, and

maintain a list in order of most recent use. 




Submit a single file named RollNo_11.cpp