結果
問題 | No.1098 LCAs |
ユーザー | risujiroh |
提出日時 | 2020-06-26 21:37:25 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 303 ms / 2,000 ms |
コード長 | 3,596 bytes |
コンパイル時間 | 2,432 ms |
コンパイル使用メモリ | 213,684 KB |
実行使用メモリ | 33,508 KB |
最終ジャッジ日時 | 2023-09-18 03:28:05 |
合計ジャッジ時間 | 7,355 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 1 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 | 2 ms
4,376 KB |
testcase_15 | AC | 2 ms
4,376 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,376 KB |
testcase_18 | AC | 236 ms
22,116 KB |
testcase_19 | AC | 227 ms
22,032 KB |
testcase_20 | AC | 226 ms
22,140 KB |
testcase_21 | AC | 226 ms
22,196 KB |
testcase_22 | AC | 223 ms
22,096 KB |
testcase_23 | AC | 151 ms
22,640 KB |
testcase_24 | AC | 153 ms
22,532 KB |
testcase_25 | AC | 135 ms
22,648 KB |
testcase_26 | AC | 146 ms
22,576 KB |
testcase_27 | AC | 142 ms
22,484 KB |
testcase_28 | AC | 288 ms
32,704 KB |
testcase_29 | AC | 280 ms
33,508 KB |
testcase_30 | AC | 303 ms
32,308 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define DEBUG(...) #endif template <class T = int> struct tree { struct edge { int from, to; T w; int operator-(int v) const { return from ^ to ^ v; } }; int n; vector<edge> es; vector<vector<int>> g; vector<int> pv, pe, sz, dep, vs, in, out, head; vector<T> dist; tree(int _n = 0) : n(_n), g(n) {} void add(int u, int v, T w = 1) { g[u].push_back(size(es)), g[v].push_back(size(es)); es.push_back({u, v, w}); } void dfs(int v) { sz[v] = 1; for (int id : g[v]) { if (id == pe[v]) continue; int to = es[id] - v; assert(pv[to] == -1); pv[to] = v, pe[to] = id; dep[to] = dep[v] + 1, dist[to] = dist[v] + es[id].w; dfs(to); sz[v] += sz[to]; } sort(begin(g[v]), end(g[v]), [&](int a, int b) { return sz[es[a] - v] * (a != pe[v]) > sz[es[b] - v] * (b != pe[v]); }); } void build(int r = 0) { assert((int)size(es) == n - 1); pv.assign(n, -1), pe.resize(n), sz.resize(n), dep.resize(n), dist.resize(n); pe[r] = -1, dep[r] = 0, dist[r] = 0; dfs(r); } void dfs_hld(int v) { in[v] = size(vs), vs.push_back(v); for (int id : g[v]) { if (id == pe[v]) continue; int to = es[id] - v; head[to] = to == es[g[v][0]] - v ? head[v] : to; dfs_hld(to); } out[v] = size(vs); } void build_hld(int r = 0) { build(r); vs.clear(), in.resize(n), out.resize(n), head.resize(n); head[r] = r; dfs_hld(r); } bool anc(int u, int v) const { return in[u] <= in[v] and out[v] <= out[u]; } int lca(int u, int v) const { while (true) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) return u; v = pv[head[v]]; } } int d(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } T len(int u, int v) const { return dist[u] + dist[v] - 2 * dist[lca(u, v)]; } int la(int v, int d) const { assert(0 <= d and d <= dep[v]); while (dep[head[v]] > d) v = pv[head[v]]; return vs[in[head[v]] + (d - dep[head[v]])]; } int next(int from, int to) const { assert(from != to); if (not anc(from, to)) return pv[from]; return la(to, dep[from] + 1); } vector<pair<int, int>> ascend(int from, int to) const { vector<pair<int, int>> res; while (head[from] != head[to]) { res.emplace_back(in[from], in[head[from]]); from = pv[head[from]]; } if (from != to) res.emplace_back(in[from], in[to] + 1); return res; } vector<pair<int, int>> descend(int from, int to) const { if (from == to) return {}; if (head[from] == head[to]) return {{in[from] + 1, in[to]}}; auto res = descend(from, pv[head[to]]); res.emplace_back(in[head[to]], in[to]); return res; } template <class F> void run(int from, int to, F f, bool vertex = true) const { int v = lca(from, to); for (auto e : ascend(from, v)) f(e.first + 1, e.second); if (vertex) f(in[v], in[v] + 1); for (auto e : descend(v, to)) f(e.first, e.second + 1); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; tree g(n); for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; --u, --v; g.add(u, v); } g.build(); vector<long long> a(n); for (int v = 0; v < n; ++v) { a[v] = g.sz[v]; a[v] *= a[v]; } for (int v = 0; v < n; ++v) { long long res = a[v]; for (int id : g.g[v]) { if (id == g.pe[v]) continue; res -= a[g.es[id] - v]; } cout << res << '\n'; } }