adplus-dvertising

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¬†1‚ȧLi‚ȧRi‚ȧN1‚ȧ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¬†NN,¬†QQ¬†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¬†N‚ąí1N‚ąí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,¬†L‚Ä≤1,R‚Ä≤1,L‚Ä≤2,R‚Ä≤2,‚Ķ,L‚Ä≤k,R‚Ä≤kL1‚Ä≤,R1‚Ä≤,L2‚Ä≤,R2‚Ä≤,‚Ķ,Lk‚Ä≤,Rk‚Ä≤.
    • Let¬†xx¬†be the answer to the previous query (and¬†00¬†if this is the first query). Then,¬†Li=L‚Ä≤i‚äē(x‚čÖb),Ri=R‚Ä≤i‚äē(x‚čÖb)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

  • 1‚ȧN,Q‚ȧ5‚čÖ1051‚ȧN,Q‚ȧ5‚čÖ105
  • b‚ąą{0,1}b‚ąą{0,1}
  • 1‚ȧk‚ȧ5‚čÖ1051‚ȧk‚ȧ5‚čÖ105
  • The sum of¬†kk¬†over all queries doesn’t exceed¬†5‚čÖ1055‚čÖ105
  • 1‚ȧLi‚ȧRi‚ȧN1‚ȧLi‚ȧRi‚ȧN¬†for all valid¬†ii
  • Ri<Li+1Ri<Li+1¬†for all valid¬†ii.

Subtasks

  • Subtask 1 (10 points):
    • 1‚ȧN‚ȧ20001‚ȧN‚ȧ2000,
    • The sum of¬†kk¬†over all queries doesn’t exceed¬†20002000
    • b=0b=0
  • Subtask 2 (25 points):
    • 1‚ȧN‚ȧ1051‚ȧ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¬†L‚Ä≤1=5,R‚Ä≤1=4,x=1L1‚Ä≤=5,R1‚Ä≤=4,x=1, and hence¬†L1=5‚äē1=4,R1=4‚äē1=5L1=5‚äē1=4,R1=4‚äē1=5.

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.

If You Want To Learn Something New Then Visit Our Official Channel YOUTUBE

Related Posts

Leave a Reply

Your email address will not be published.