Bananas Multiplier (Easy/Hard)

Quiz

• https://www.hackerrank.com/contests/yfkpo3-2/challenges/bananas-multiplier-easy
• https://www.hackerrank.com/contests/yfkpo3-2/challenges/bananas-multiplier-hard

(hardも通る)解法

• (0-indexedとする)
• 頂点0からの最短距離（辺の本数）を各頂点について求める
  • bfsなり、ダイクストラなりで
• 各頂点にたどり着いた時のcの積をそれぞれ求める。これは直前の点の値が分かればO(1)で求まるので、全体ではO(N)で求まる
  • メモ化再帰なり、dpなりで
• 例えば下記画像で、頂点２～頂点５までの積を求めたいなら、「頂点０～５までの積」÷「頂点０～２までの積」で求まる
  • modの世界なので割り算は逆元で処理する

• 画像のように、頂点aから頂点bに行くときに、頂点0を挟むかどうかの場合がある
• LCAをlog(N)で求められるように前準備しておけば、除去する辺は求まる
• 実は、どちらの場合であっても統一的に処理できる。下記コード参照

// 関数fは、頂点0からその頂点に行くまでのcの積とする

// クエリ処理
ll Q;cin>>Q;
while(Q--){
  ll a,b,banana;cin>>a>>b>>banana;
  a--;b--;

  ll lca = LCA(a,b);
  ll ans = banana * f(a) % mod * f(b) % mod;
  ans *= mod_pow(f(lca), mod-2); ans %= mod;
  ans *= mod_pow(f(lca), mod-2); ans %= mod;
  p(ans);
}

計算量

• O(Q log(N) ) : クエリ数ｘLCAのコスト

要素

• 最短距離
• メモ化再帰 or DP
• 逆元
• LCA