Cerinta completa

Fedya is a seasoned traveller and is planning his trip to Treeland. Treeland is a country with an ancient road system which is in the form of a tree structure. cities of Treeland are numbered by positive integers: .

Fedya has not yet decided the starting point (city) of his journey and the cities he will visit. But there are a few things you know about Fedya’s trip:

  • Fedya is fond of travelling to great distances. So if he is currently located in city , his destination will be a city which is most distant from city .

  • There might be more than 1 such cities. In that case, Fedya will choose a city that was already visited as less times as possible in this journey.

  • There still might be more than 1 such cities. In that case, Fedya will go to the city with the smallest number.

Fedya has prepared a list of possible journeys. Each one is characterized by two integers – the starting city and the total number of cities to be visited, . For each of them, he is keen to know the total distance travelled by him.

Input Format

The first line of input will contain two space separated integers and – the number of cities and the number of possible journeys.

Then, there will be lines, each of them will contain two space separated integers , denoting the bi-directional road between the cities with numbers and with the unitary length.

Then there will be lines, each of them will have two space separated integers and , denoting a journey.

Constraints



Output Format

For each journey, output the travelled distance on a separate line.

Sample Input

8 7
2 1
3 2
4 2
5 1
6 1
7 1
8 7
4 6
3 4
6 3
7 6
4 6
7 1
2 6

Sample Output

24
16
11
23
24
3
23

Explanation

The tree in question is given in the picture below.

image

  • 4 6 indicates that Fedya starts at 4. Now we see that the most distant city from 4 is 8. Fedya now travels to city 8. From 8, the most distance cities are [4, 3]. As 4 is already visited, he chooses to visit city 3. From city 3, he revisits city 8 and so on. The cities in the order of visit is 4 – > 8 -> 3 -> 8 -> 4 -> 8 -> 3 which sums to 24. Hence, the answer.
  • 6 3 indicates that Fedya starts at city 6. From 6, the most distant cities are [3,4,8]. In this leg of the journey, no city is visited and hence Fedya chooses to visit the city with the smallest number 3. From 3, he visits 8 and then he ends his trip at city 4 which sums to 3 + 4 + 4 = 11. Hence, the answer.

Limbajul de programare folosit: cpp14

Cod:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

vector<int> visit;
int len;

int dfs(vector<map<int, int> >& g, int node, int dist) {
    //cout << "dfs " << node << " dist " << dist << endl;
    visit[node] = 1;
    int max1 = dist, max2 = 0, max_dep = 0;
    for(auto iter = g[node].begin(); iter != g[node].end(); ++iter) {
        if(iter->second >= max1) {
            max2 = max1;
            max1 = iter->second;
        } else {
            max2 = max(iter->second, max2);
        }
    }
    //cout << "nod " << node << " max " << max1 << " " << max2 << endl;
    for(auto iter = g[node].begin(); iter != g[node].end(); ++iter) {
        if(visit[iter->first]) {
            iter->second = dist;
        } else {
            iter->second = dfs(g, iter->first, 1 + (iter->second != max1 ? max1 : max2));
            max_dep = max(max_dep, iter->second);
        }
    }
    for(auto it2 = g[node].begin(); it2 != g[node].end(); ++it2) {
        //cout << "(" << it2->first << ", " <<it2->second << ") ";
    }
    //cout << endl << len << endl;
    len = max(len, dist);
    return max_dep + 1;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<map<int, int> > g(n);
    for(int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        g[a - 1][b - 1] = 0;
        g[b - 1][a - 1] = 0;
    }
    visit.assign(n, 0);
    dfs(g, 0, 0);
    visit.assign(n, 0);
    dfs(g, 0, 0);
    /*
    for(auto it1 = g.begin(); it1 != g.end(); ++it1) {
        for(auto it2 = (*it1).begin(); it2 != (*it1).end(); ++it2) {
            cout << "(" << it2->first << ", " <<it2->second << ") ";
        }
        cout << endl;
    }*/
    
    //cout << "len " << len << endl;
    
    while(m--) {
        int v, dist = 0;
        long long k, sum = 0;
        cin >> v >> k;
        for(auto iter = g[v - 1].begin(); iter != g[v - 1].end(); ++iter) {
            dist = max(dist, iter->second);
        }
        sum = dist + (k - 1) * len;
        cout << sum << endl;
    }
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464647248

Link challenge: https://www.hackerrank.com/challenges/journey-scheduling/problem

Journey Scheduling