Dual Distance DUALDIST SOLUTION

by

Dual Distance DUALDIST

Given a tree with N nodes, answer Q queries of the following type:

a,b (where a≠b) which asks you to calculate ∑Ni=1min(dist(i,a),dist(i,b)) where dist(x,y) is the number of edges on the shortest path between the nodes x and y in the tree.
Note: The input and output of this problem are large, so prefer using fast input/output methods.

Input
The first line contains an integer T, the number of test cases. Then the test cases follow.
Each test case contains N+Q lines of input.
The first line contains two integers N and Q.
The next N−1 lines each contains two integers u, v representing an edge between nodes u and v in the tree.
The next Q lines each contains two integers a, b, the nodes considered for the respective query.
Output
For each query of each test case, output the answer in a new line.

Constraints
1≤T≤8
2≤N≤105
1≤Q≤105
a≠b
The sum of N over all test cases is at most 5⋅105.
The sum of Q over all test cases is at most 5⋅105.
Its guaranteed that the given input is a valid tree.
Subtasks
Subtask #1 (20 points):

2≤N≤103
1≤Q≤103
The sum of N over all test cases is at most 5⋅103.
The sum of Q over all test cases is at most 5⋅103.
Time limit: 0.5 sec.
Subtask #2 (80 points):

original constraints
Time limit: 2 sec.
Sample Input
2
4 2
1 2
2 3
3 4
1 2
3 1
7 1
1 2
1 3
2 4
2 5
3 6
3 7
2 6
Sample Output
3
2
6
Explanation:
Test Case 1:

Query 1: Answer = min(dist(1,1),dist(1,2)) + min(dist(2,1),dist(2,2)) + min(dist(3,1),dist(3,2)) + min(dist(4,1),dist(4,2)) = min(0,1) + min(1,0) + min(2,1) + min(3,2) = 0+0+1+2 = 3.

Query 2: Answer = min(dist(1,1),dist(1,3)) + min(dist(2,1),dist(2,3)) + min(dist(3,1),dist(3,3)) + min(dist(4,1),dist(4,3)) = min(0,2) + min(1,1) + min(2,0) + min(3,1) = 0+1+0+1 = 2.

Program:

#include <iostream>
#include<vector>
#include<queue>
#include <climits>
#include <cstdint>
#include <iterator>
#include <algorithm>
using namespace std;

 void bfs(int a,int b,vector<int> graph[],int vertices){
    int seen[vertices];
    int seen2[vertices];
    for(int i=0;i<vertices;i++){
        seen[i]=0;
        seen2[i]=0;
    }
    queue<int> queue;
    int distance[vertices];
    int distance2[vertices];
    for(int i=0;i<vertices;i++){
        distance[i] = INT_MAX;
        distance2[i] = INT_MAX;
    }
    seen[a]=1;
    seen2[b]=1;
    queue.push(a);
    distance[a]=0;
    distance2[b]=0;
   
    while(!queue.empty()){
        int pop = queue.front();
        queue.pop();
        for(int i=0;i<graph[pop].size();i++){
            int ver = graph[pop][i];
            if(seen[ver]==1) continue;
            seen[ver]=1;
            queue.push(ver);
            distance[ver] = distance[pop]+1;
        }
    }
    queue.push(b);
    while(!queue.empty()){
        int pop = queue.front();
        queue.pop();
        for(int i=0;i<graph[pop].size();i++){
            int ver = graph[pop][i];
            if(seen2[ver]==1) continue;
            seen2[ver]=1;
            queue.push(ver);
            distance2[ver] = distance2[pop]+1;
        }
    }
    
    int dist = 0;
    for(int k=0;k<vertices;k++){
        // cout<<distance[k]<<"\n";
        // cout<<distance2[k]<<"\n";
        dist+=min(distance[k],distance2[k]);
    }
    cout<<dist<<"\n";
    
}

int main() {
	// your code goes here
	int t;
	cin>>t;
	for(int i=0;i<t;i++){
	    int n,q;
	    cin>>n;
	    cin>>q;

	    vector<int> graph[n];
	    for(int j=0;j<n-1;j++){
	        int a,b;
	        cin>>a;
	        cin>>b;
	        graph[a-1].push_back(b-1);
            graph[b-1].push_back(a-1);
	    }
	    
	    for(int j=0;j<q;j++){
	        int a,b;
	        cin>>a;
	        cin>>b;
	        bfs(a-1,b-1,graph,n);
	    }
	}
	return 0;
}

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :