#486684 (C++17) No.1098 LCAs

• 問題: No.1098 LCAs
• ユーザー: しの
• 提出日時: 2020-05-25 02:10:46
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 854 bytes
• コンパイル時間: 2,168 ms
• コンパイル使用メモリ: 207,972 KB
• 実行使用メモリ: 31,872 KB
• 最終ジャッジ日時: 2024-11-22 16:24:09
• 合計ジャッジ時間: 5,431 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	2 ms; 5,248 KB
testcase_12	AC	2 ms; 5,248 KB
testcase_13	AC	3 ms; 5,248 KB
testcase_14	AC	3 ms; 5,248 KB
testcase_15	AC	2 ms; 5,248 KB
testcase_16	AC	2 ms; 5,248 KB
testcase_17	AC	3 ms; 5,248 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-

ソースコード

// 乗算オーバーフロー

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<vector<int>> graph;
vector<int> sz, par;
vector<ll> result;

void dfs(int v) {
  sz[v] = 1;
  for (auto u : graph[v]) if (par[v] != u) {
    par[u] = v;
    dfs(u);
    sz[v] += sz[u];
  }
}

void dfs2(int v) {
  for (auto u : graph[v]) if (par[v] != u) {
    result[v] -= result[u];
    dfs2(u);
  }
}

int main() {
  cin.tie(0); ios_base::sync_with_stdio(false);


  int n; cin >> n;
  graph.resize(n);
  for (int i = 0; i < n-1; i++) {
    int u, v; cin >> u >> v;
    u--; v--;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  sz.assign(n, 0); par.assign(n, -1);
  dfs(0);

  result.resize(n);
  for (int v = 0; v < n; v++)
    result[v] = sz[v] * sz[v];

  dfs2(0);

  for (int v = 0; v < n; v++)
    cout << result[v] << '\n';
}