あなたのツリーは一般的なツリーです。つまり、バランスがとれているとか、根を持つという概念さえありませんO(n)。O(n)ただし、一度時間がかかるツリーを設定すると、後続の各クエリに一定の時間がかかるようになると思います。
アイデアは、ツリーをほぼ同じサイズのツリーに分割するツリーの「中間」を見つけ、その部分を任意の部分、たとえばleftとrightと呼ぶことです。次に、それぞれのパーツのすべてのノードにそれらが含まれるパーツでラベルを付け、中央から最も離れた左右のノードを格納します。ノードのクエリを取得すると、ノードのラベルを見て、反対側に格納されているノードを報告するだけです。
コメント[および不当な反対票]を考えると、解決策にはもう少し説明が必要なようです. まず、特定のノードの最も離れたノードは、一般に一意ではありません。たとえば、ちょうど 3 つのノードを持つパスを想像してください。中間ノードには、最も離れたノードが 2 つあります。いずれかが解決策です。それに基づいて、ツリー内で最も離れた 2 つのノード間のパスの中央にあるノードをツリー内で見つけることが考えられます (これらのノード間の距離が奇数である場合、どちらかの側のノードを選択できます)。距離が 1 つだけ異なる場合): 最も離れたノードがlノード離れている場合、中間ノードには、それらの両方への長さl/2のパス、またはl/2から 1 とl/2+1のパスがあります。もう一方に。
この中間ノードを使用して、ツリーをランダムに左半分と右半分と呼ばれる 2 つの半分に分割すると、各ノードが左半分にあるか右半分にあるかを知っている場合、特定のノードの最も離れたノードを決定できます。最長パスは、中央のノードを通過して残りの半分に入り、そこから中央から最も離れたノードに移動します。左部分の最長パスの長さをll、右部分の最長パスの長さをlrと呼びましょう。一般性を失うことなく、lr < llとします (名前を入れ替えるだけです)。中央から最も離れたそれぞれのノードはnlおよびnrと呼ばれます. 最長パス (または一意の場合は最長パス) の 1 つが左側部分にある限り、中間ノードから続く複数のサブツリーが右側部分の一部と見なされても問題ないことに注意してください。
ノードnから最も離れたノードを指定する場合、考慮すべき 3 つのケースがあります。
残っている唯一の問題は、O(n)時間内に中間ノードを見つける方法です。
1距離を与えます0。これはO(n)時間[および空間]で実行できます。最後のパスとして、最大の距離ラベルを持つ隣接ノードを見つけ、このノードからぶら下がっているツリーを左側のツリーと見なします。ノードを BFS で左ノードとしてラベル付けしながら、キュー内の最後のノードを追跡してnlを見つけます。他のすべてのサブツリーを正しいツリーと見なし、それらにも正しいノードとして BFS のラベルを付け、nrも見つけます。
おそらくいくつかのパスを使用して、ツリーの前処理をよりエレガントに行うことができると思いますが、上記のアプローチが機能すると確信しています。