Header Ads Widget

Tree Interval Queries CodeChef Solution

 

We Are Discuss About CODECHEF SOLUTION

Tree Interval Queries CodeChef Solution

Tree Interval Queries CodeChef Solution

You are given a tree with NN vertices numbered 1,2,,N1,2,…,N. First, you sort the adjacency lists of all the vertices and run depth first search from node 11. This gives you an array of dfs start times. Note that the start times are uniquely determined, as the adjacency list of each vertex is sorted. The following code represents the dfs:

    // let st denote the start times
    // let adj[x] be the adjacency list (the list of neighbors) of x
    int timer = 1;
    void dfs(int s, int p){
        st[s] = timer;
        timer++;
        // iterate over the neighbors in increasing order
        sort(adj[s].begin(), adj[s].end());
        for(int v: adj[s]) {
            if(v != p){
                dfs(v, s);
            }
        }
    }

The timer is initialized with 11 in the beginning, and you call dfs(1,0)(1,0) to compute all the start times. Let stvstv denote the start time of vv.

Now, you have to process QQ queries.

Each query contains an integer kk and a list of disjoint intervals [L1,R1],[L2,R2],,[Lk,Rk][L1,R1],[L2,R2],…,[Lk,Rk], where 1LiRiN1≤Li≤Ri≤N for all valid ii and Ri<Li+1Ri<Li+1 for all valid ii. Let SS be the set of vertices whose start time lies in one of the intervals [Li,Ri][Li,Ri]. Then, the answer for a query is the number of connected components in the graph, whose set of vertices is SS, and the edges are the edges of the tree with both endpoints in SS.

You are also given an integer bb in the beginning of the input, which is 00 if you can process the queries offline and 11 if you must process them online (see input description for more clarity).

Input Format

  • The first line contains NNQQ and bb, the number of vertices, the number of queries and an integer denoting whether you must process the queries online.
  • Each of the next N1N−1 lines contains two integers, aa and bb denoting the endpoints of an edge.
  • The following lines contain the queries. Each query contains 2 lines:
    • The first line of each query contains kk, the number of intervals
    • The second line contains 2k2k space separated integers, L1,R1,L2,R2,,Lk,RkL1′,R1′,L2′,R2′,…,Lk′,Rk′.
    • Let xx be the answer to the previous query (and 00 if this is the first query). Then, Li=Li(xb),Ri=Ri(xb)Li=Li′⊕(x⋅b),Ri=Ri′⊕(x⋅b) for all valid ii, where  denotes the bitwise xor operator.

Output Format

For each query, print one line containing the number of connected components in the graph described in the problem statement.

Tree Interval Queries CodeChef Solution

Constraints

  • 1N,Q51051≤N,Q≤5⋅105
  • b{0,1}b∈{0,1}
  • 1k51051≤k≤5⋅105
  • The sum of kk over all queries doesn't exceed 51055⋅105
  • 1LiRiN1≤Li≤Ri≤N for all valid ii
  • Ri<Li+1Ri<Li+1 for all valid ii.

Subtasks

  • Subtask 1 (10 points):
    • 1N20001≤N≤2000,
    • The sum of kk over all queries doesn't exceed 20002000
    • b=0b=0
  • Subtask 2 (25 points):
    • 1N1051≤N≤105,
    • The sum of kk over all queries doesn't exceed 105105
    • b=0b=0
  • Subtask 3 (30 points): b=0b=0
  • Subtask 4 (35 points): b=1b=1

Sample Input 1 

6 2 0
1 3
1 2
2 4
2 5
3 6
2
1 3 5 6
1
4 5

Sample Output 1 

1
2

Explanation

Tree Interval Queries CodeChef Solution

The tree is the following (with start times written inside brackets):

.

In the first query, the valid start times are {1,2,3,5,6}{1,2,3,5,6} and hence the set SS is {1,2,3,4,6}{1,2,3,4,6}, and this set forms a single connected component.

In the second query, the valid start times are {4,5}{4,5} and hence the set SS is {3,5}{3,5}, and this set forms two connected components.

Sample Input 2 

6 2 1
1 3
1 2
2 4
2 5
3 6
2
1 3 5 6
1
5 4

Sample Output 2 

1
2

Explanation

This is the same as the previous sample but with b=1b=1. Note that, for the second testcase L1=5,R1=4,x=1L1′=5,R1′=4,x=1, and hence L1=51=4,R1=41=5L1=5⊕1=4,R1=4⊕1=5.

Post a Comment

0 Comments