結果
| 問題 | No.1718 Random Squirrel |
| ユーザー |
👑  emthrm
|
| 提出日時 | 2021-10-23 00:18:46 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 220 ms / 2,000 ms |
| コード長 | 10,346 bytes |
| コンパイル時間 | 3,178 ms |
| コンパイル使用メモリ | 230,992 KB |
| 最終ジャッジ日時 | 2025-01-25 04:40:25 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 |
ソースコード
#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;}