## topCoder

BAN USER- 0of 0 votes

AnswersAps Island has many cities. In the summer, many travellers will come to the island and attend festive

- topCoder in United States

events in different cities. The festive events in Aps Island are crazy. Once it starts, it will never end. In

the following sentences, the cities which have festive events are called festive cities.

At the beginning, only city No. 1 is festive city. If a new city becomes festive city, the government will tell

the information center about this news.

Everyday, the information center will receive many inquiries from travellers from different cities of this

land. They want to know the closest festive city, and calculate the distance (If current city has festive

event, the distance is 0).

Due to the growing number of the travellers, the information center is overloaded. The government

wants to fix the problem by developing a system to handle the inquiries automatically.

As a fact, cities in Aps Island are connected with highways(bidirectional, length of every highway is 1).

Any two cities are connected directly or indirectly, and there is ONLY one path between any 2 cities.

Input

There are two integers in the first line, n (2 ≤ n ≤ 105) and m ( 1 ≤ m ≤ 105), n is the number of cities in

the Aps Island and m is the number of queries. The coming n-1 lines are the highways which connect

two cities. In the line, there are two integers ai and bi (1 ≤ ai, bi ≤ n, ai≠ bi), representing two cities.

Each line means the highway connecting the two cities.

Next m lines are inquiries from travellers or news from government. Each line has two integers qi

and ci (1 ≤ qi ≤ 2, 1 ≤ ci ≤ n). If qi = 1, the government announces a new festive city ci. If qi = 2, you have

to find and print the shortest distance from the city ci to the closest festive city.

Output

Results from each (qi = 2) Questions. Print every result with a new line.

input

5 5

1 2

1 3

3 4

3 5

2 5

2 3

1 3

2 3

2 4

output

2

1

0

1| Report Duplicate | Flag | PURGE

WAP - 0of 0 votes

AnswersAps Island has many cities. In the summer, many travellers will come to the island and attend festive

- topCoder

events in different cities. The festive events in Aps Island are crazy. Once it starts, it will never end. In

the following sentences, the cities which have festive events are called festive cities.

At the beginning, only city No. 1 is festive city. If a new city becomes festive city, the government will tell

the information center about this news.

Everyday, the information center will receive many inquiries from travellers from different cities of this

land. They want to know the closest festive city, and calculate the distance (If current city has festive

event, the distance is 0).

Due to the growing number of the travellers, the information center is overloaded. The government

wants to fix the problem by developing a system to handle the inquiries automatically.

As a fact, cities in Aps Island are connected with highways(bidirectional, length of every highway is 1).

Any two cities are connected directly or indirectly, and there is ONLY one path between any 2 cities.

Input

There are two integers in the first line, n (2 ≤ n ≤ 105) and m ( 1 ≤ m ≤ 105), n is the number of cities in

the Aps Island and m is the number of queries. The coming n-1 lines are the highways which connect

two cities. In the line, there are two integers ai and bi (1 ≤ ai, bi ≤ n, ai≠ bi), representing two cities.

Each line means the highway connecting the two cities.

Next m lines are inquiries from travellers or news from government. Each line has two integers qi

and ci (1 ≤ qi ≤ 2, 1 ≤ ci ≤ n). If qi = 1, the government announces a new festive city ci. If qi = 2, you have

to find and print the shortest distance from the city ci to the closest festive city.

Output

Results from each (qi = 2) Questions. Print every result with a new line.

input

5 5

1 2

1 3

3 4

3 5

2 5

2 3

1 3

2 3

2 4

output

2

1

0

1| Report Duplicate | Flag | PURGE

- 0of 0 votes

AnswersThere is a garden of strawberry plants represented by a 2D, square array.Each plant represents an element in the matrix ie it has a number of strawberries. If a plant doesnt have strawberries it is denoted by 0. If 0 is encountered you cannot travel through that path.

- topCoder in United States

You can start from any cell along the left border of this ground (i.e the matrix) and travel until it finally stops at one cell in the right border, and you can only move to up/down/right. You can only visit each cell once. Calculate the maximum number of berries is obtained.

Backtracking using Dynamic programming is one of the methods i have thought of.

Also there some special conditions:

a.Even in the left border and right border, we can go up and down.

b. When we are at the top cell of one column, we can still go up, which demands us to

pay all current strawberries , then we will be teleported to the bottom cell of this column and vice

versa.

Input: user enters dimensions of ground ie size of matrix and the matrix itself

Output: is the maximum number of strawberries collected without encountering 0; in case we do we display 0.

Till now i have managed to find the largest value in the first column of the matrix but i am facing difficulty in testing the neighbours of that cell.

Also i am not able to store the position of the cell which i started from or even mark it.

Input

4 4

-1 4 5 1

2 -1 2 4

3 3 -1 3

4 2 1 2

output

23

Input

4 4

-1 4 5 1

2 -1 2 4

3 3 -1 -1

4 2 1 2

output

22| Report Duplicate | Flag | PURGE

Walmart Labs Algorithm C++ Coding Dynamic Programming - 0of 0 votes

AnswersThere is a dictionary with few words each of length 3 and start and finish word is given. You can reach from one word to another word by changing only one digit. Like from cat, you can reach to hat or bat or cap. What is the minimum number of steps should be taken to reach finish word from start word

- topCoder in India| Report Duplicate | Flag | PURGE

Coupon Dunia SDE1 Algorithm - 0of 0 votes

AnswersGiven three arrays sorted in non-decreasing order, print all common elements in these arrays.

- topCoder in India

Examples:

ar1[] = {1, 5, 10, 20, 40, 80}

ar2[] = {6, 7, 20, 80, 100}

ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}

Output: 20, 80

ar1[] = {1, 5, 5}

ar2[] = {3, 4, 5, 5, 10}

ar3[] = {5, 5, 10, 20}

Outptu: 5, 5| Report Duplicate | Flag | PURGE

Coupon Dunia SDE1 Algorithm Data Structures - 0of 0 votes

Answersquicksort takes O(n2) when elements are sorted what is the solution to reduce it to O(nlogn)?

- topCoder in India| Report Duplicate | Flag | PURGE

SDE1 Algorithm

RepShastri Ji is well known hindi and tamil vashikaran specialist. He will give you effective and simple totke to control ...

Rep**alicesreedg**, Accountant at ADPHi my name is Alice and i am working in an IT company. I am working here from last 5 ...

Rep**melodyakeel**, Consultant at ProgressHello I am Melody. I am working as Human resource clerks, also called human resource assistants. I can maintain employee ...

Rep**stacimdalton**, Dev Lead at ASAPInfosystemsPvtLtdAt the moment I'm implementing Slinkies in the financial sector. My current pet project is researching break up a ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Segment tree could be one possible solution but don't know how to change this problem in Segment tree, any suggestions?

- topCoder September 28, 2015