結果

問題 No.1098 LCAs
ユーザー HaarHaar
提出日時 2020-06-26 22:04:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 336 ms / 2,000 ms
コード長 2,472 bytes
コンパイル時間 2,370 ms
コンパイル使用メモリ 207,772 KB
実行使用メモリ 27,384 KB
最終ジャッジ日時 2023-09-18 04:40:14
合計ジャッジ時間 7,437 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 3 ms
4,380 KB
testcase_15 AC 3 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 252 ms
17,864 KB
testcase_19 AC 255 ms
17,760 KB
testcase_20 AC 242 ms
17,652 KB
testcase_21 AC 254 ms
17,816 KB
testcase_22 AC 250 ms
17,812 KB
testcase_23 AC 166 ms
17,744 KB
testcase_24 AC 168 ms
17,888 KB
testcase_25 AC 157 ms
17,968 KB
testcase_26 AC 192 ms
17,972 KB
testcase_27 AC 182 ms
18,268 KB
testcase_28 AC 336 ms
26,284 KB
testcase_29 AC 333 ms
27,384 KB
testcase_30 AC 321 ms
26,256 KB
権限があれば一括ダウンロードができます

ソースコード

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