Submission #229952

---

Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define SZ(a) int((a).size())
#define PB push_back
#define MP make_pair

#define MAX_V 100001
#define INF 100000

struct edge{int to,cost;};
typedef pair<int,int> P;//firstは最短距離,secondは頂点番号

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s){
	priority_queue<P,vector<P>,greater<P> > que;
	fill(d,d+V,INF);
	d[s]=0;
	que.push(P(0,s));
	
	while(!que.empty()){
		P p=que.top();que.pop();//仮の最短距離が短い順に取り出す
		int v=p.second;
		if(d[v]<p.first)continue;
		REP(i,G[v].size()){
			edge e=G[v][i];
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				que.push(P(d[e.to],e.to));//仮の最短距離と頂点の組を更新が行われる度に追加していく
			}
		}
	}
}
int main(){
	int N;
	cin>>N;
	V=N;
	REP(i,N-1){
		int x,y;
		cin>>x>>y;
		x--;y--;
		edge e1,e2;
		e1.to=y;e1.cost=1;
		e2.to=x;e2.cost=1;
		G[x].PB(e1);
		G[y].PB(e2);
	}
	int Q;
	cin>>Q;
	vector<int>res;
	REP(i,Q){
		int a,b;
		cin>>a>>b;
		a--;b--;
		dijkstra(a);
		res.PB(d[b]+1);
	}
	REP(i,Q){
		cout<<res[i]<<endl;
	}
	return 0;
}

Submission Info

Judge Result