WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。ヴァーサは2つの無向木を持っている。それぞれの木はn個の頂点を持っている。それらの頂点には0からn-1の番号が、特に順序は考えられずに振られている。2つの木の形は違うこともある。tree1とtree2が与えられる。1番目の木において、番号iの頂点はtree1[i]番目の頂点と辺で繋がっている。同様に、2番目の木において、番号iの頂点はtree2[i]番目の頂点と辺で繋がっている。ヴァーサはこれら2つの木が相似度を計算してみた。それを彼は2つのステップで行った。e2)の値を定義した。e2))の総和を2つの木の相似度と定義した。e2)を定義するときは、下記のような手順を踏むことにした。1番目の木から、辺e1を取り除くと2つの木に分割される。この中から1つ選び、それをAと呼ぶ。2番目の木から、辺e2を取り除くと2つの木に分割される。この中から1つ選び、それをBと呼ぶ。AとBの両方に存在する頂点のセットをXとする。(AとBの選択がXのサイズに影響する)与えられた2つの木の相似度を返せ。4000考えたこと今、仮にAとBを選択済みだとして、選択されていない方をA'、B'とする。すると、計算したいのは次の4パターンとなる。AとBを選択したときのXのサイズAとB'を選択したときのXのサイズA'とBを選択したときのXのサイズA'とB'を選択したときのXのサイズこいつらは、どれか1つでも計算できれば簡単にだせる。頂点数をn、Aの頂点数をa、Bの頂点数をbとする。AとBを選択したときのXのサイズをxとする。すると、4パターンそれぞれの計算方法は次のようになる。e2)を全探索したとしても、それらでaとbとxを一瞬で出せればOKとなる。Aの頂点数aを考える。もらった1番目の木の辺情報で、どれか1つをe1として決め打ちする。それでdfsなどすれば、頂点集合Aとその頂点数a、並びにどの頂点がAに所属しているかを出せる。aの取得はこれでOK。次にBの頂点数bとxを考える。2番目の木をdfsして、現在着目している頂点vで、vをルートとしたサブツリーをBとする。bとxはdfsでbとxを返すようにしておけば簡単に出せる。vの全子供の頂点において、dfsを呼び出し、そこで返ってきたbとxを合計しておく。後はvにおいて、bは1足せばいいし、xはvがAに含まれるなら1足せばよい。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。