結果
問題 | No.1718 Random Squirrel |
ユーザー | 👑 emthrm |
提出日時 | 2021-10-23 00:18:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 253 ms / 2,000 ms |
コード長 | 10,346 bytes |
コンパイル時間 | 3,838 ms |
コンパイル使用メモリ | 239,180 KB |
実行使用メモリ | 56,844 KB |
最終ジャッジ日時 | 2024-09-24 08:06:20 |
合計ジャッジ時間 | 7,907 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 126 ms
33,180 KB |
testcase_12 | AC | 23 ms
8,704 KB |
testcase_13 | AC | 80 ms
21,224 KB |
testcase_14 | AC | 124 ms
34,332 KB |
testcase_15 | AC | 139 ms
29,472 KB |
testcase_16 | AC | 54 ms
15,616 KB |
testcase_17 | AC | 110 ms
31,640 KB |
testcase_18 | AC | 202 ms
39,356 KB |
testcase_19 | AC | 123 ms
28,484 KB |
testcase_20 | AC | 37 ms
13,952 KB |
testcase_21 | AC | 189 ms
46,032 KB |
testcase_22 | AC | 253 ms
47,068 KB |
testcase_23 | AC | 183 ms
46,048 KB |
testcase_24 | AC | 184 ms
46,156 KB |
testcase_25 | AC | 249 ms
46,992 KB |
testcase_26 | AC | 90 ms
47,400 KB |
testcase_27 | AC | 95 ms
47,396 KB |
testcase_28 | AC | 89 ms
47,400 KB |
testcase_29 | AC | 107 ms
51,360 KB |
testcase_30 | AC | 114 ms
56,652 KB |
testcase_31 | AC | 113 ms
56,844 KB |
testcase_32 | AC | 106 ms
51,364 KB |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 1000000007; // constexpr int MOD = 998244353; constexpr int DY[]{1, 0, -1, 0}, DX[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}, DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; struct EulerTour { std::vector<int> tour, left, right, down, up, depth; EulerTour(const std::vector<std::vector<int>> &graph, int root = 0) : graph(graph) { int n = graph.size(); left.resize(n); right.resize(n); down.assign(n, -1); up.assign(n, (n - 1) << 1); int idx = 0; dfs(-1, root, 0, idx); } template <typename Fn> void v_update(int ver, Fn f) const { f(left[ver], right[ver] + 1); } template <typename T, typename Fn> T v_query(int ver, Fn f) const { return f(left[ver], right[ver] + 1); } template <typename T, typename Fn> T e_query(int u, int v, Fn f) const { return f(down[u] + 1, down[v] + 1); } template <typename Fn> void subtree_e_update(int ver, Fn f) const { f(down[ver] + 1, up[ver]); } template <typename T, typename Fn> T subtree_e_query(int ver, Fn f) const { return f(down[ver] + 1, up[ver]); } private: const std::vector<std::vector<int>> graph; void dfs(int par, int ver, int now_depth, int &idx) { left[ver] = tour.size(); tour.emplace_back(ver); depth.emplace_back(now_depth); for (int e : graph[ver]) { if (e != par) { down[e] = idx++; dfs(ver, e, now_depth + 1, idx); tour.emplace_back(ver); depth.emplace_back(now_depth); up[e] = idx++; } } right[ver] = tour.size() - 1; } }; struct LowestCommonAncestorByDoubling { std::vector<int> depth, dist; LowestCommonAncestorByDoubling(const std::vector<std::vector<int>> &graph) : graph(graph) { n = graph.size(); depth.resize(n); dist.resize(n); while ((1 << table_h) <= n) ++table_h; parent.resize(table_h, std::vector<int>(n)); } void build(int root = 0) { is_built = true; dfs(-1, root, 0, 0); for (int i = 0; i + 1 < table_h; ++i) for (int ver = 0; ver < n; ++ver) { parent[i + 1][ver] = parent[i][ver] == -1 ? -1 : parent[i][parent[i][ver]]; } } int query(int u, int v) const { assert(is_built); if (depth[u] > depth[v]) std::swap(u, v); for (int i = 0; i < table_h; ++i) { if ((depth[v] - depth[u]) >> i & 1) v = parent[i][v]; } if (u == v) return u; for (int i = table_h - 1; i >= 0; --i) { if (parent[i][u] != parent[i][v]) { u = parent[i][u]; v = parent[i][v]; } } return parent[0][u]; } int distance(int u, int v) const { assert(is_built); return dist[u] + dist[v] - dist[query(u, v)] * 2; } private: bool is_built = false; int n, table_h = 1; std::vector<std::vector<int>> graph, parent; void dfs(int par, int ver, int now_depth, int now_dist) { depth[ver] = now_depth; dist[ver] = now_dist; parent[0][ver] = par; for (int e : graph[ver]) { if (e != par) dfs(ver, e, now_depth + 1, now_dist + 1); } } }; struct HeavyLightDecomposition { std::vector<int> parent, subtree, id, inv, head; HeavyLightDecomposition(const std::vector<std::vector<int>> &graph, int root = 0) : graph(graph) { int n = graph.size(); parent.assign(n, -1); subtree.assign(n, 1); id.resize(n); inv.resize(n); head.resize(n); dfs1(root); head[root] = root; int now_id = 0; dfs2(root, now_id); } template <typename Fn> void v_update(int u, int v, Fn f) const { while (true) { if (id[u] > id[v]) std::swap(u, v); f(std::max(id[head[v]], id[u]), id[v] + 1); if (head[u] == head[v]) return; v = parent[head[v]]; } } template <typename T, typename F, typename G> T v_query(int u, int v, F f, G g, const T ID) const { T left = ID, right = ID; while (true) { if (id[u] > id[v]) { std::swap(u, v); std::swap(left, right); } left = g(left, f(std::max(id[head[v]], id[u]), id[v] + 1)); if (head[u] == head[v]) break; v = parent[head[v]]; } return g(left, right); } template <typename Fn> void subtree_v_update(int ver, Fn f) const { f(id[ver], id[ver] + subtree[ver]); } template <typename T, typename Fn> T subtree_v_query(int ver, Fn f) const { return f(id[ver], id[ver] + subtree[ver]); } template <typename Fn> void e_update(int u, int v, Fn f) const { while (true) { if (id[u] > id[v]) std::swap(u, v); if (head[u] == head[v]) { f(id[u], id[v]); break; } else { f(id[head[v]] - 1, id[v]); v = parent[head[v]]; } } } template <typename T, typename F, typename G> T e_query(int u, int v, F f, G g, const T ID) const { T left = ID, right = ID; while (true) { if (id[u] > id[v]) { std::swap(u, v); std::swap(left, right); } if (head[u] == head[v]) { left = g(left, f(id[u], id[v])); break; } else { left = g(left, f(id[head[v]] - 1, id[v])); v = parent[head[v]]; } } return g(left, right); } template <typename Fn> void subtree_e_update(int ver, Fn f) const { f(id[ver], id[ver] + subtree[ver] - 1); } template <typename T, typename Fn> T subtree_e_query(int ver, Fn f) const { return f(id[ver], id[ver] + subtree[ver] - 1); } int lowest_common_ancestor(int u, int v) const { while (true) { if (id[u] > id[v]) std::swap(u, v); if (head[u] == head[v]) return u; v = parent[head[v]]; } } private: std::vector<std::vector<int>> graph; void dfs1(int ver) { for (int &e : graph[ver]) { if (e != parent[ver]) { parent[e] = ver; dfs1(e); subtree[ver] += subtree[e]; if (subtree[e] > subtree[graph[ver].front()]) std::swap(e, graph[ver].front()); } } } void dfs2(int ver, int &now_id) { id[ver] = now_id++; inv[id[ver]] = ver; for (int e : graph[ver]) { if (e != parent[ver]) { head[e] = (e == graph[ver].front() ? head[ver] : e); dfs2(e, now_id); } } } }; template <typename Abelian> struct FenwickTreeSupportingRangeAddQuery { FenwickTreeSupportingRangeAddQuery(int n_, const Abelian ID = 0) : n(n_), ID(ID) { ++n; dat_const.assign(n, ID); dat_linear.assign(n, ID); } void add(int left, int right, Abelian val) { if (right < ++left) return; for (int i = left; i < n; i += i & -i) { dat_const[i] -= val * (left - 1); dat_linear[i] += val; } for (int i = right + 1; i < n; i += i & -i) { dat_const[i] += val * right; dat_linear[i] -= val; } } Abelian sum(int idx) const { Abelian res = ID; for (int i = idx; i > 0; i -= i & -i) res += dat_linear[i]; res *= idx; for (int i = idx; i > 0; i -= i & -i) res += dat_const[i]; return res; } Abelian sum(int left, int right) const { return left < right ? sum(right) - sum(left) : ID; } Abelian operator[](const int idx) const { return sum(idx, idx + 1); } private: int n; const Abelian ID; std::vector<Abelian> dat_const, dat_linear; }; int main() { int n, k; cin >> n >> k; vector<vector<int>> graph(n); REP(_, n - 1) { int u, v; cin >> u >> v; --u; --v; graph[u].emplace_back(v); graph[v].emplace_back(u); } vector<int> d(k); REP(i, k) cin >> d[i], --d[i]; EulerTour euler_tour(graph, d.front()); sort(ALL(d), [&](int a, int b) -> bool { return euler_tour.left[a] < euler_tour.left[b]; }); // REP(i, k) cerr << d[i] << " \n"[i + 1 == k]; LowestCommonAncestorByDoubling lca(graph); lca.build(d.front()); ll steiner = 0; REP(i, k) steiner += lca.distance(d[i], d[(i + 1) % k]); // cerr << steiner << '\n'; HeavyLightDecomposition hld(graph, d.front()); FenwickTreeSupportingRangeAddQuery<ll> bit(n); REP(i, k) hld.v_update(d[i], d[(i + 1) % k], [&](int u, int v) -> void { bit.add(u, v, 1); }); vector<int> dist(n, -1), from(n, -1); queue<int> que; REP(i, n) { if (bit[hld.id[i]] > 0) { dist[i] = 0; from[i] = i; que.emplace(i); } } while (!que.empty()) { int ver = que.front(); que.pop(); for (int e : graph[ver]) { if (dist[e] == -1) { dist[e] = dist[ver] + 1; from[e] = from[ver]; que.emplace(e); } } } // REP(i, n) cerr << dist[i] << " \n"[i + 1 == n]; vector<int> has_acorn(n, false); REP(i, k) has_acorn[d[i]] = true; vector<vector<pair<int, int>>> child(n); auto f = [&](auto&& f, int par, int ver) -> void { for (int e : graph[ver]) { if (e == par) continue; f(f, ver, e); if (!child[e].empty()) { child[ver].emplace_back(child[e].front().first + 1, e); } else if (has_acorn[e]) { child[ver].emplace_back(1, e); } } sort(ALL(child[ver]), greater{}); }; f(f, -1, d.front()); auto g = [&](auto&& g, int par, int ver, int pd) -> void { if (par != -1) { child[ver].emplace_back(pd, par); sort(ALL(child[ver]), greater{}); } for (int e : graph[ver]) { if (e == par) continue; if (child[ver].empty()) { assert(has_acorn[ver]); g(g, ver, e, 1); } else if (child[ver].front().second == e) { if (child[ver].size() == 1) { assert(has_acorn[ver]); g(g, ver, e, 1); } else { g(g, ver, e, child[ver][1].first + 1); } } else { g(g, ver, e, child[ver].front().first + 1); } } }; g(g, -1, d.front(), 0); REP(i, n) cout << steiner + dist[i] - (child[from[i]].empty() ? 0 : child[from[i]].front().first) << '\n'; return 0; }