sum of all cost between all nodes in a tree ～木の全点間コストの和～

Quiz

https://yukicoder.me/problems/no/872

AC

https://yukicoder.me/submissions/404193

解法

• まずはganariyaさんの解説を読みましょう
  • https://scrapbox.io/ganariya/YukicoderContest221_C%E5%95%8F%E9%A1%8CP2_%E3%80%8CAll_Tree_Path%E3%80%8D

• そこに書かれている通り、あるエッジを使う回数は「エッジの向こう側」ｘ「エッジのこちら側」
• dfsで「エッジの向こう側」の数が求められればよい

// i以降のノード数を返す
// (iも含む)
ll dfs(ll i, ll prev){
  ll sum = 0;
  for(auto edge : G[i]){
    if(edge.to==prev) continue;
    sum += dfs(edge.to, i);
  }

  ll a = sum+1;
  ll b = N-a;
  ll d = dist2(i, prev);
  ans += a*b*d;

  return sum+1;
}

その他

• タイトルをgooglability高い感じにした

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?