結果
問題 | No.1098 LCAs |
ユーザー |
![]() |
提出日時 | 2021-04-11 20:52:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 399 ms / 2,000 ms |
コード長 | 2,221 bytes |
コンパイル時間 | 1,334 ms |
コンパイル使用メモリ | 97,956 KB |
最終ジャッジ日時 | 2025-01-20 16:12:27 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
// Template#include <iostream>#include <vector>#include <algorithm>#include <numeric>#include <iomanip>#include <tuple>#include <utility>#include <queue>#include <set>#include <map>#define rep_override(x, y, z, name, ...) name#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)#define all(x) (x).begin(), (x).end()using namespace std;using ll = long long;constexpr int inf = 1001001001;constexpr ll infll = 3003003003003003003LL;template <typename T>inline bool chmin(T &x, const T &y) {if (x > y) {x = y;return true;}return false;}template <typename T>inline bool chmax(T &x, const T &y) {if (x < y) {x = y;return true;}return false;}template <typename T>istream &operator>>(istream &is, vector<T> &vec) {for (T &element : vec) is >> element;return is;}template <typename T>ostream &operator<<(ostream &os, const vector<T> &vec) {for (int i = 0, vec_len = (int)vec.size(); i < vec_len; ++i) {os << vec[i] << (i + 1 == vec_len ? "" : " ");}return os;}struct IOSET {IOSET() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);}} ioset;// Mainint main() {int n;cin >> n;vector<vector<int>> g(n);rep(i, n - 1) {int u, v;cin >> u >> v;--u;--v;g[u].push_back(v);g[v].push_back(u);}vector<int> sz(n, 0);auto dfs_sz = [&](auto &&dfs, int v, int p) -> int {int ret = 1;for (int u : g[v]) {if (u == p) continue;ret += dfs(dfs, u, v);}return sz[v] = ret;};dfs_sz(dfs_sz, 0, -1);vector<ll> ans(n, 0);rep(i, n) ans[i] = (ll)sz[i] * sz[i];auto dfs_second = [&](auto &&dfs, int v, int p) -> void {for (int u : g[v]) {if (u == p) continue;ans[v] -= ans[u];dfs(dfs, u, v);}};dfs_second(dfs_second, 0, -1);rep(i, n) cout << ans[i] << "\n";}