TreeColoring

Please note that this problem has a non-standard time limit: 4 seconds.

Dimas is very fond of trees, he really enjoys solving problems on trees. Recently, his professor Rohit gave him a very difficult task to solve. This is it:

You're given a tree on N vertices. (A tree is an undirected connected graph with no cycles.) Different edges of the tree may have different lengths. Initially, all vertices are white. You now have to process Q queries. There are two types of queries:

• type 1: Given a node x, paint it blue.
• type 2: Given a node x, compute the sum of all distances between x and a blue node.

You are given the ints N, Q, startSeed, threshold, and maxDist. Use the algorithm given below as pseudocode to generate both the tree and the sequence of queries you should process.

int curValue = startSeed;

int genNextRandom() {
    curValue = (curValue * 1999 + 17) % 1000003;
    return curValue;
}

void generateInput() {
    for (int i = 0; i < N-1; i++) {
        distance[i] = genNextRandom() % maxDist;
	parent[i] = genNextRandom();
        if (parent[i] < threshold) {
            parent[i] = i;
        } else {
            parent[i] = parent[i] % (i + 1);
        }
    }

    for (int i = 0; i < Q; i++) {
        queryType[i] = genNextRandom() % 2 + 1;
        queryNode[i] = genNextRandom() % N;
    }
}

The output of the above pseudocode are four arrays: parent, distance, queryType, and queryNode.

The arrays parent and distance have N-1 elements each. For each valid i, our tree contains an edge between the vertices (i+1) and parent[i]. The length of that edge is distance[i]. Note that parent[i] will always be between 0 and i, inclusive.

The arrays queryType and queryNode have Q elements each. For each valid i, the i-th query (0-based index) you should process has the type queryType[i], and should be applied to the vertex queryNode[i]. The queries must be processed in the given order.

Return the bitwise XOR of the answers to all type 2 queries.