結果

問題 No.1098 LCAs
ユーザー HaarHaar
提出日時 2020-06-26 22:04:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 494 ms / 2,000 ms
コード長 2,472 bytes
コンパイル時間 3,219 ms
コンパイル使用メモリ 200,024 KB
最終ジャッジ日時 2025-01-11 11:29:59
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

/**
 * @title Graph template
 * @docs graph_template.md
 */
template <typename Cost = int> class Edge{
public:
  int from,to;
  Cost cost;
  Edge() {}
  Edge(int to, Cost cost): to(to), cost(cost){}
  Edge(int from, int to, Cost cost): from(from), to(to), cost(cost){}
};

template <typename T> using Graph = std::vector<std::vector<Edge<T>>>;
template <typename T> using Tree = std::vector<std::vector<Edge<T>>>;

template <typename T, typename C> void add_edge(C &g, int from, int to, T w = 1){
  g[from].emplace_back(from, to, w);
}

template <typename T, typename C> void add_undirected(C &g, int a, int b, T w = 1){
  add_edge<T, C>(g, a, b, w);
  add_edge<T, C>(g, b, a, w);
}

/**
 * @title Rooting
 * @docs rooting.md
 */
template <typename T>
void rooting(Tree<T> &tree, int cur, int par = -1){
  if(par != -1){
    for(auto it = tree[cur].begin(); it != tree[cur].end(); ++it){
      if(it->to == par){
        tree[cur].erase(it);
        break;
      }
    }
  }

  for(auto &e : tree[cur]){
    rooting(tree, e.to, cur);
  }
}

/**
 * @title Fixed point combinator
 * @docs fix_point.md
 */
template <typename F>
struct FixPoint : F{
  explicit constexpr FixPoint(F &&f) noexcept : F(std::forward<F>(f)){}

  template <typename... Args>
  constexpr auto operator()(Args &&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
inline constexpr auto make_fix_point(F &&f){
  return FixPoint<F>(std::forward<F>(f));
}

template <typename F>
inline constexpr auto make_fix_point(F &f){
  return FixPoint<F>(std::forward<F>(f));
}



int main(){
  int N;

  while(std::cin >> N){
    Tree<int> tree(N);
    for(int i = 0; i < N-1; ++i){
      int v, w; std::cin >> v >> w;
      --v, --w;

      add_undirected(tree, v, w, 1);
    }

    rooting(tree, 0);

    std::vector<int64_t> sub(N);

    auto f =
      make_fix_point(
        [&](auto &&f, int cur) -> int64_t {
          sub[cur] = 1;

          for(auto &e : tree[cur]){
            sub[cur] += f(e.to);
          }

          return sub[cur];
        }
      )(0);
    


    for(int k = 0; k < N; ++k){
      int64_t ans = 0;

      ans += 1;
      ans += (sub[k] - 1) * 2;

      int64_t s = 0;
      for(auto &e : tree[k]){
        s += sub[e.to];
      }

      for(auto &e : tree[k]){
        ans += sub[e.to] * (s - sub[e.to]);
      }
      
      


      std::cout << ans << "\n";
    }
  }
  
  

  return 0;
}
0