Submission #230662

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cmath>
#include <climits>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
#define ALL(x) (x).begin(),(x).end()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define MP make_pair
#define PB push_back
#define SORT(c) sort((c).begin(),(c).end())
#define SZ(x) int((x).size())

#define TIMES(i, n)         for(int i = 0; i < (n); i++)
#define UP_UNTIL(i, a, b)   for(int i = (a); i < (b); i++)
#define UP_TO(i, a, b)      for(int i = (a); i <= (b); i++)
#define DOWN_UNTIL(i, a, b) for(int i = (a); i > (b); i--)
#define DOWN_TO(i, a, b)    for(int i = (a); i >= (b); i--)
#define LOOP                while(true)
#define ITER(c, i)          for(auto i = (c).begin(); i != (c).end(); i++)
#define KEY first
#define VALUE second
#define NEARLY_EQUAL(a, b)  (abs((a) - (b)) <= EPS)

typedef unsigned long long ulonglong;
typedef unsigned long ulong;
typedef unsigned short ushort;

const long long  LLINF =  LLONG_MAX / 3; // >= 9223372036854775807
const long        LINF =   LONG_MAX / 3; // >= 2147483647
const short       SINF =   SHRT_MAX / 2; // >= 32767
const ushort     USINF =  USHRT_MAX / 2; // >= 65535
const double      DINF = 1 / 0.0;
const double EPS = 1e-10;

const double PI = acos(-1.0); // =~ 3.1415926535897931

int N;
vector<vector<ushort> > pass;
vector<vector<ulong> > dist;
bool changed;

long cdist(int i, int j){
	ITER(pass[i], x) dist[i][*x] = 1;
	do{
		changed = false;
		TIMES(k, N){
			if(dist[i][k] == LINF) continue;
			ITER(pass[k], l){
				if(i == *l) continue;
				if(dist[i][k] + 1 < dist[i][*l]){
					dist[i][*l] = dist[i][k] + 1;
					changed = true;
				}
			}
		}
	}while(changed);
	return dist[i][j];
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> N;
	dist = vector<vector<ulong> >(N);
	TIMES(i, N){
		dist[i] = vector<ulong>(N);
		TIMES(j, N) dist[i][j] = LINF;
	}
	pass = vector<vector<ushort> >(N);
	TIMES(i, N){
		pass[i] = vector<ushort>();
	}
	TIMES(i, N - 1){
		int x, y;
		cin >> x >> y;
		pass[x-1].PB(y-1);
		pass[y-1].PB(x-1);
	}
	int Q;
	cin >> Q;
	TIMES(i, Q){
		int x, y;
		cin >> x >> y;
		if(dist[x - 1][y - 1] != LINF)
			cout << dist[x - 1][y - 1] + 1 << endl;
		else if(dist[y - 1][x - 1] != LINF)
			cout << dist[y - 1][x - 1] + 1 << endl;
		else
			cout << cdist(x - 1, y - 1) + 1 << endl;
	}
	return 0;
}

Submission Info

Judge Result