採点プログラムのサンプルファイル
factories.zip問題
IOI 国には 0 から N - 1 までの互いに異なる番号の付けられた N 個の街があり，それらの間は N - 1 個の双方向に通行可能な道路で結ばれている．どの街からどの街へもいくつかの道路をたどって行くことができる．
IOI 国には，特殊な部品を製造する会社がたくさんある．これらの会社は，それぞれ異なる 1 種類の部品を製造している．各会社は 1 つ以上の街に工場を置いており，複数の会社が同じ街に工場を置いていることもある．
会社は他社の部品を必要とすることが時々ある．その際には，その会社の工場から，自社の工場まで部品を輸送してくる必要がある．部品を運んでくる他社の工場はどの街の工場でもよいし，部品を運ぶ先の自社の工場はどの街の工場でもよい．部品の輸送元と輸送先の工場をうまく選ぶことで，部品の輸送距離をできるだけ短くしたい．
課題
まず，IOI 国の街の数，道路の情報が与えられる．その後，街 Xj,0, ..., Xj,Sj-1 に工場を持つ会社 Uj が，街 Yj,0, ..., Yj,Tj-1 に工場を持つ会社 Vj の部品を必要としている，という形の質問が Q 個与えられる．それぞれの質問に対し，部品を輸送するのに必要な距離の最小値を返すプログラムを作成せよ．
実装の詳細
あなたは，各質問に正しく答える方法を実装した 1 個のプログラムを書かねばならない．プログラムは，#include "factories.h" を行うこと．
プログラムは，以下のルーチンを実装しなければならない．
- void Init(int N, int A[], int B[], int D[])
- long long Query(int S, int X[], int T, int Y[])
このルーチンは，最初に 1 回だけ呼び出される．引数 N は，IOI 国にある街の数である．引数 A, B, D は，長さ N - 1 の配列であり，要素 A[i], B[i], D[i] は，3 つの整数 Ai, Bi, Di である (0 ≤ i ≤ N - 2)．これは，それぞれの i (0 ≤ i ≤ N - 2) について，番号 Ai の街と番号 Bi の街を結ぶ長さ Di の道路が存在することを表す．
この関数は，Q 個の質問ごとにそれぞれ呼び出される．質問 j において，引数 S, T は，2 つの整数 Sj, Tj であり，それぞれ会社 Uj, Vj が工場を置いている街の数を表す．配列 X は，長さ Sj の配列であり，要素 X[0], X[1], ..., X[S-1] は，会社 Uj が工場を置いている街の番号を表す．配列 Y は，長さ Tj の配列であり，要素 Y[0], Y[1], ..., Y[T-1] は，会社 Vj が工場を置いている街の番号を表す．この関数は，会社 Uj の工場に会社 Vj の工場から部品を輸送するために必要な距離の最小値を返さなければならない．
コンパイル・実行の方法
作成したプログラムをテストするための，採点プログラムのサンプルが，コンテストサイトからダウンロードできるアーカイブの中 factories.zip に含まれている．このアーカイブには，提出しなければならないファイルのサンプルも含まれている．
採点プログラムのサンプルは 1 つのファイルからなる．そのファイルは grader.c または grader.cpp である．例えば，作成したプログラムを factories.c または factories.cpp とするとき，作成したプログラムをテストするには，次のようにコマンドを実行する．
- C の場合
- C++ の場合
gcc -O2 -std=c11 -o grader grader.c factories.c -lm
g++ -O2 -std=c++11 -o grader grader.cpp factories.cpp
コンパイルが成功すれば， grader という実行ファイルが生成される．
実際の採点プログラムは，採点プログラムのサンプルとは異なることに注意すること．採点プログラムのサンプルは単一のプロセスとして起動する．このプログラムは，標準入力から入力を読み込み，標準出力に結果を出力する．
採点プログラムのサンプルの入力
採点プログラムのサンプルは標準入力から以下の入力を読み込む．
- 1 行目には整数 N, Q が空白を区切りとして書かれており，それぞれ IOI 国の街の数，プログラムに与えられる質問の数を表す．
- 続く N - 1 行のうちの i + 1 行目 (0 ≤ i ≤ N - 2) には，整数 Ai, Bi, Di が空白を区切りとして書かれており，番号 Ai の街と番号 Bi の街を結ぶ長さ Di の道路が存在することを表す．
- 続く 3Q 行のうちの 3j + 1 行目から 3j + 3 行目 (0 ≤ j ≤ Q - 1) には，質問 j の情報が書かれている．
3j + 1 行目 (0 ≤ j ≤ Q - 1) には，整数 Sj, Tj (1 ≤ Sj ≤ N - 1, 1 ≤ Tj ≤ N - 1) が空白を区切りとして書かれており，会社 Uj, Vj が工場を置いている街の数がそれぞれ Sj, Tj であることを表す．
3j + 2 行目 (0 ≤ j ≤ Q - 1) には Sj 個の整数 Xj,0, ..., Xj,Sj-1 が空白を区切りとして書かれている．これは，会社 Uj が工場を番号 Xj,0, ..., Xj,Sj-1 の街に置いていることを表す．
3j + 3 行目 (0 ≤ j ≤ Q - 1) には Tj 個の整数 Yj,0, ..., Yj,Tj-1 が空白を区切りとして書かれている．これは，会社 Vj が工場を番号 Yj,0, ..., Yj,Tj-1 の街に置いていることを表す．
採点プログラムのサンプルの出力
プログラムの実行が正常に終了した場合，採点プログラムのサンプルは，標準出力へ Query の返り値を 1 行に 1 つずつ順に出力する．
制限
すべての入力データは以下の条件を満たす.
- 2 ≤ N ≤ 500 000．
- 1 ≤ Q ≤ 100 000.
- 0 ≤ Ai ≤ N - 1 (0 ≤ i ≤ N - 2).
- 0 ≤ Bi ≤ N - 1 (0 ≤ i ≤ N - 2).
- 1 ≤ Di ≤ 100 000 000 (0 ≤ i ≤ N - 2).
- Ai ≠ Bi (0 ≤ i ≤ N - 2).
- どの 2 つの街の間も，いくつかの道路を経由して移動することができる．
- 1 ≤ Sj ≤ N - 1 (0 ≤ j ≤ Q - 1)．
- 0 ≤ Xj,k ≤ N - 1 (0 ≤ j ≤ Q - 1, 0 ≤ k ≤ Sj - 1)．
- 1 ≤ Tj ≤ N - 1 (0 ≤ j ≤ Q - 1)．
- 0 ≤ Yj,k ≤ N - 1 (0 ≤ j ≤ Q - 1, 0 ≤ k ≤ Tj - 1)．
- Xj,0, Xj,1, ..., Xj,Sj-1, Yj,0, Yj,1, ..., Yj,Tj-1 は互いに異なる (0 ≤ j ≤ Q - 1)．
- S0 + S1 + ··· + SQ-1 ≤ 1 000 000.
- T0 + T1 + ··· + TQ-1 ≤ 1 000 000.
小課題
小課題 1 [15 点]
以下の条件を満たす．
- N ≤ 5 000．
- Q ≤ 5 000．
小課題 2 [18 点]
以下の条件を満たす．
- Si ≤ 10 (0 ≤ i ≤ Q - 1)．
- Ti ≤ 10 (0 ≤ i ≤ Q - 1)．
小課題 3 [67 点]
追加の制限はない．
入出力例
入力例
7 3 0 1 4 1 2 4 2 3 5 2 4 6 4 5 5 1 6 3 2 2 0 6 3 4 3 2 0 1 3 4 6 1 1 2 5
出力例
12 3 11
この入力例は，採点プログラムのサンプルに与えるデータの例である．また，この出力例は，正しいプログラムを実行した際に，採点プログラムのサンプルが標準出力へ出力するデータである．
この入力例においては，
- 質問 0 において，会社 U0 は街 0, 6 に，会社 V0 は街 3, 4 に工場を置いている．このとき，街 3 にある会社 V0 の工場から，街 6 にある会社 U0 の工場に部品を輸送するのが最も輸送距離が短くなり，このときの輸送距離は 12 になる．
- 質問 1 において，会社 U1 は街 0, 1, 3 に，会社 V1 は街 4, 6 に工場を置いている．このとき，街 6 にある会社 V1 の工場から，街 1 にある会社 U1 の工場に部品を輸送するのが最も輸送距離が短くなり，このときの輸送距離は 3 になる．
- 質問 2 において，会社 U2 は街 2 に，会社 V2 は街 5 に工場を置いている．このとき，街 5 にある会社 V2 の工場から，街 2 にある会社 U2 の工場に部品を輸送するのが最も輸送距離が短くなり，このときの輸送距離は 11 になる．