Coloring Tree
You are given a tree with N nodes with every node being colored. A color is represented by an integer ranging from 1 to 109. Can you find the number of distinct colors available in a subtree rooted at the node s? Input Format The first line contains three space separated integers representing the number of nodes in the tree (N), number of queries to answer (M) and the root of the tree. In each of the next N-1 lines, there are two space separated integers(a b) representing an edge from
View Solution →Recalling Early Days GP with Trees
You are given a tree with N nodes and each has a value associated with it. You are given Q queries, each of which is either an update or a retrieval operation. The update query is of the format i j X This means you'd have to add a GP series to the nodes which lie in the path from node i to node j (both inclusive) with first term of the GP as X on node i and the common ratio as R (given in the input) The retrieval query is of the format i j You need to return the sum of the node v
View Solution →Swaps and Sum
You are given a sequence a1, a2, a3, . . . an. The task is to perform the following queries on it: Type 1. Given two integers l and r( 1 <= l <= r ; r - l +1 is even ) . Reorder the elements of the sequence in such a way (changed part of the sequence is in brackets): That is swap the first two elements of segment [ l , r ] , the second two elements, and so on. Type 2. Given two integers l and r, print the value of sum . Input Format The first line contains two integers n and q.
View Solution →Coolguy and Two Subsequences
Coolguy gives you a simple problem. Given a 1-indexed array, A , containing N elements, what will ans be after this pseudocode is implemented and executed? Print ans % ( 10^9 + 7 ). //f(a, b) is a function that returns the minimum element in interval [a, b] ans = 0 for a -> [1, n] for b -> [a, n] for c -> [b + 1, n] for d -> [c, n] ans = ans + min(f(a, b), f(c, d)) Input Format The first line contains N (the size of array A). The s
View Solution →Subtrees And Paths
Given a rooted tree of N nodes, where each node is uniquely numbered in between [1..N]. The node 1 is the root of the tree. Each node has an integer value which is initially 0. You need to perform the following two kinds of queries on the tree: add t value: Add value to all nodes in subtree rooted at t max a b: Report maximum value on the path from a to b Input Format First line contains N, number of nodes in the tree. Next N-1 lines contain two space separated integers x and y whic
View Solution →