Submission #255358

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <math.h>
#include <map>
#include <list>
#include <vector>
#include <set>

#define MAX_NUM_NODE (100000)

using namespace std;

double log2(double a)
{
	return (log(a)/log(2));
}

static int sN = 0;
static vector<int> sDepth;
static vector<vector<int> > sAncestorsOfNodes;
static vector<list<int> > sEdges; // 双方向リンクを示す
static vector<pair<int, int> > sTestEdges;

void buildParentsAndDepthsByDFS(int node, int parent, int depth)
{
	// cout << "[depth="<<depth<<"]: <parent="<<parent<<"> :<node=" << node <<">"<<endl;
	// depth first search
	sDepth[node] = depth;
	sAncestorsOfNodes[node].resize((int)ceil(log2(sN)));
	sAncestorsOfNodes[node][0] = parent;

	list<int>::iterator itChild;
	for(itChild=sEdges[node].begin();
			itChild!=sEdges[node].end();
			itChild++) {
		if((*itChild)==parent) {
			continue;
		}
		buildParentsAndDepthsByDFS(*itChild, node, depth+1);
	}
}

void buildAncestors()
{
	// 全部のNodeの 2^gen 世代前の祖先をたどる。
	for(int gen=0; gen > (int)ceil(log2(sN)); gen++) {
		// 浅い世代から、全NodeについてAncestorを埋めていく。
		// cout << "gen=" <<gen<< endl;
		// cout << "(int)ceil(log2(sN))=" <<(int)ceil(log2(sN))<< endl;
		for(int node=0; node<sN; node++) {
			// cout << "gen=" <<gen<<", node=" << node<< endl;
			// sAncestorsOfNodes
			int ancestorAtGen = sAncestorsOfNodes[node][gen];
			if(0>ancestorAtGen) {
				sAncestorsOfNodes[node][gen+1] = sAncestorsOfNodes[ancestorAtGen][gen];
			}
			else {
				sAncestorsOfNodes[node][gen+1] = -1;
			}
		}
	}
}

int lca(int node1, int node2)
{
	if(sDepth[node1]>sDepth[node2]) {
		swap(node1, node2);
	}

	int gen=0;
	for(int newNode2=node2;
			sDepth[node1]<sDepth[newNode2];
			gen++) {
		node2 = newNode2;
		newNode2 = sAncestorsOfNodes[node2][gen];
	}
	while(sDepth[node1]<sDepth[node2]) {
		node2 = sAncestorsOfNodes[node2][0];
	}

	// the same depth
	gen = 0;
	for(int newNode1=node1, newNode2=node2;
			newNode1!=newNode2;
			gen++) {
		node1 = newNode1;
		node2 = newNode2;
		newNode1 = sAncestorsOfNodes[node1][gen];
		newNode2 = sAncestorsOfNodes[node2][gen];
	}
	while(node1!=node2) {
		node1 = sAncestorsOfNodes[node1][0];
		node2 = sAncestorsOfNodes[node2][0];
	}
	return node1;
}

int main(int argc, char *argv[])
{
    cin >> sN;
	sDepth.resize(sN);
	sEdges.resize(sN);
	sAncestorsOfNodes.resize(sN);

	// cout << "point-2" <<endl;

	for(int n=0; n<sN-1; n++) {
		int x=-1, y=-1;
        cin >> x;
        cin >> y;
		// cout <<"x="<<x<<",y="<<y<<endl;
		sEdges[x-1].push_back(y-1);
		sEdges[y-1].push_back(x-1);
	}

	// cout << "point-1" <<endl;

	int Q = 0;
    cin >> Q;

    sTestEdges.resize(Q);

	for(int q=0; q<Q; q++) {
		int a=-1, b=-1;
		cin >> a;
		cin >> b;
		sTestEdges[q].first = a-1;
		sTestEdges[q].second= b-1;
		// cout<<"[q="<<q<<"]:a="<<a<<",b="<<b<<endl;
	}
	// cout << "point0" <<endl;

	int root = 0;

	//=====初期化終了=====
	// cout << "point1" <<endl;

	buildParentsAndDepthsByDFS(0, -1, 0);
	// cout << "point2" <<endl;

	buildAncestors();

	// cout << "point3" <<endl;

	int lowestCommonAncestor = -1;
	for(int q=0; q<Q; q++) {
		int a = sTestEdges[q].first;
		int b = sTestEdges[q].second;
		lowestCommonAncestor = lca(a, b);
		int distance
			= sDepth[a]+sDepth[b]
			- 2*lowestCommonAncestor;

		cout << distance+1 << endl;
	}


    return 0;
}

Submission Info

Judge Result