UVa 10938 : Flea circus

問題概要：
木とクエリーが与えられる
クエリーは以下の形式で与えられる
a b
a,bはそれぞれ木のノード番号を表す
それらのノードにはノミが存在し、以下の条件を満たしながらお互い引き合うように移動する
1回の移動で以下の条件を満たした上で隣接するノードに移動することができる
ノミは同時に移動する

・ノミはあるノードまたは葉から別のノードまたは葉に、これまで通った道を通らずに移動する道がちょうど１つ存在する

・ノミはあるノードまたは葉から別のノードまたは葉が枝でつながれている場合のみ移動することができる

そして、以下の状態になった場合そのノード番号を指定された形式にしたがって出力せよ

・もし同時に二匹のノミが同時に同じ場所についたならば二匹のノミはそこで長い間話をし続ける

・もし同時に二匹のノミが同時に隣接する場所についたならば二匹のノミはそこで永遠にジャンプし続ける

解法：
Lowest Common Ancestorをみつけて木を一直線にし、それらの場所を出力する
一直線になおした木のノード数が奇数なら真ん中のノードに同時に到着する
偶数なら真ん中のノードとその１つ前のノードで永遠にジャンプし続ける
木のルートは特に指定されないので葉でないノードを適当にルートとする

コード：

//LCAは蟻本参照

int parent[MAX_V];
int node_depth[MAX_V];
void makeParent(int cur,int p,int d)
{
  if(parent[cur] != -1)return;
  parent[cur] = p; 
  node_depth[cur] = d;
  rep(i,G[cur].size())makeParent(G[cur][i],cur,d+1);
}

void getUpRoute(int cur,int target,vector<int> &route)
{
  route.push_back(cur);
  if(cur == target)return;
  getUpRoute(parent[cur],target,route);
}
  

int main()
{
  while(1)
    {
      scanf("%d",&V);
      if(V == 0)break;

      rep(i,V)G[i].clear(),parent[i] = -1;

      rep(i,V-1)
	{
	  int a,b;
	  scanf("%d %d",&a,&b);
	  a--,b--;
	  G[a].push_back(b);
	  G[b].push_back(a);
	}
      
      rep(i,V)if(G[i].size() != 1)
	{
	  root = i;
	  break;
	}

      makeParent(root,root,0);

      RMQ<ii> rmq;
      init(V,rmq);
      scanf("%d",&query);

      int s,t;
      while(query--)
	{
	  scanf("%d %d",&s,&t);
	  s--,t--;
	  int LCA = lca(s,t,rmq);
	  vector<int> L,R;


	  if(node_depth[s] < node_depth[LCA])getUpRoute(LCA,s,L);
	  else                               getUpRoute(s,LCA,L);

	  if(node_depth[t] < node_depth[LCA])getUpRoute(LCA,t,R);
	  else                               getUpRoute(t,LCA,R);

	  if(L[L.size()-1] != LCA)reverse(all(L));
	  if(R[0] != LCA)reverse(all(R));

	  vector<int> Route;
	  rep(i,L.size())Route.push_back(L[i]);
	  REP(i,1,R.size())Route.push_back(R[i]);

	  int mindex = Route.size()/2;
	  if(Route.size()%2)cout << "The fleas meet at "<< 1+Route[mindex] <<".\n";
	  else              cout << "The fleas jump forever between "<< min(Route[mindex],Route[mindex-1])+1 << " and " << 1+max(Route[mindex],Route[mindex-1]) <<".\n";

	}

    }
  return 0;
}