# Dual Distance DUALDIST SOLUTION

Page Contents

## 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.

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.

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() {
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;
}

``````