結果
| 問題 | No.2491 Pochi and A Warp Machine |
| ユーザー |
 Cyanmond
|
| 提出日時 | 2023-09-26 23:03:17 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,206 ms / 3,000 ms |
| コード長 | 9,892 bytes |
| コンパイル時間 | 3,709 ms |
| コンパイル使用メモリ | 238,548 KB |
| 最終ジャッジ日時 | 2025-02-17 02:32:46 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 |
ソースコード
#include <bits/stdc++.h>#include "atcoder/dsu"using i64 = std::int64_t;struct TreeManager {int n, lg;std::vector<std::vector<int>> tree;std::vector<int> in, out, par, depth;std::vector<std::vector<int>> table;TreeManager(const std::vector<std::vector<int>> &tree_) {tree = tree_;n = (int)tree.size();lg = 0;while ((1 << lg) < n) ++lg;int id = 0;in.assign(n, 0);out.assign(n, 0);par.assign(n, 0);depth.assign(n, 0);dfs(0, -1, 0, id);constructTable();}void dfs(const int v, const int p, const int d, int &id) {in[v] = id++;depth[v] = d;par[v] = p;for (const int t : tree[v]) {if (t == p) continue;dfs(t, v, d + 1, id);}out[v] = id++;}void constructTable() {table.resize(lg);table[0] = par;for (int rank = 1; rank < lg; ++rank) {table[rank].assign(n, -1);for (int i = 0; i < n; ++i) {const int t1 = table[rank - 1][i];if (t1 == -1) table[rank][i] = -1;else table[rank][i] = table[rank - 1][t1];}}}int lca(int u, int v) {if (depth[u] > depth[v]) std::swap(u, v);for (int rank = lg - 1; rank >= 0; --rank) {const int p = table[rank][v];if (p != -1 and depth[p] >= depth[u]) v = p;}assert(depth[u] == depth[v]);if (u == v) return u;for (int rank = lg - 1; rank >= 0; --rank) {const int a = table[rank][u], b = table[rank][v];if (a != b) {u = a;v = b;}}return par[u];}int dist(int u, int v) {return depth[u] + depth[v] - 2 * depth[lca(u, v)];}};struct FenwickTree {int n;std::vector<i64> data;FenwickTree(int n_) : n(n_), data(n + 1, 0) {}void add(int i, i64 v) {++i;while (i <= n) {data[i] += v;i += i & -i;}}i64 fold(int r) {i64 ret = 0;while (r != 0) {ret += data[r];r -= r & -r;}return ret;}i64 fold(int l, int r) {return fold(r) - fold(l);}};std::vector<i64> main_(std::vector<int>, std::vector<int>);std::vector<i64> naive_(std::vector<int>, std::vector<int>);void randomTest() {static constexpr int N = 1000;std::mt19937 mt;std::uniform_int_distribution<int> dist(0, N - 1);int tests = 100;while (tests--) {std::vector<int> X, Y;int cnt = 0;atcoder::dsu uft(N);while (cnt != N - 1) {const int a = dist(mt), b = dist(mt);if (uft.same(a, b)) continue;uft.merge(a, b);X.push_back(a);Y.push_back(b);++cnt;}const auto ans = naive_(X, Y), challanger = main_(X, Y);if (ans != challanger) {std::cout << "Id : " << tests << std::endl;std::cout << N << std::endl;for (int i = 0; i < N - 1; ++i) {std::cout << X[i] << ' ' << Y[i] << std::endl;}for (const auto e : challanger) std::cout << e << ' ';std::cout << std::endl;for (const auto e : ans) std::cout << e << ' ';std::cout << std::endl << std::endl;}}}int main() {// randomTest();std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int N;std::cin >> N;std::vector<int> X(N - 1), Y(N - 1);for (int i = 0; i < N - 1; ++i) {std::cin >> X[i] >> Y[i];--X[i], --Y[i];}const auto ans = main_(X, Y);for (const auto e : ans) {std::cout << e << std::endl;}}std::vector<i64> main_(std::vector<int> X, std::vector<int> Y) {const int N = (int)X.size() + 1;std::vector<std::vector<int>> Tree(N);for (int i = 0; i < N - 1; ++i) {Tree[X[i]].push_back(Y[i]);Tree[Y[i]].push_back(X[i]);}TreeManager sTree(Tree);std::vector<int> distList(N);for (int i = 1; i < N; ++i){distList[i] = sTree.dist(i - 1, i);}FenwickTree fenTree1(N), fenTree2(N);std::vector<bool> isAvailable(N, true);std::vector<int> subSize(N);std::vector<int> dist1(N, -1), dist2(N, -1);std::vector<i64> ans(N);auto decomposite = [&](auto &&selfD, const int root) -> void {auto dfs1 = [&](auto &&self, const int v, const int p) -> int {subSize[v] = 1;dist1[v] = dist2[v] = -1;for (const int t : Tree[v]) {if (t == p) continue;if (not isAvailable[t]) continue;subSize[v] += self(self, t, v);}return subSize[v];};dfs1(dfs1, root, -1);const int s = subSize[root];auto dfs2 = [&](auto &&self, const int v, const int p) -> int {bool isCentroid = true;int ret = -1;for (const int t : Tree[v]) {if (t == p) continue;if (not isAvailable[t]) continue;const int res = self(self, t, v);if (res != -1) return res;if (subSize[t] > s / 2) isCentroid = false;}if (s - subSize[v] > s / 2) isCentroid = false;if (isCentroid) ret = v;return ret;};const int centroid = dfs2(dfs2, root, -1);std::vector<std::pair<int, int>> qs;dist1[centroid] = 0;for (const int t : Tree[centroid]) {if (not isAvailable[t]) continue;std::vector<std::pair<int, int>> qsc;auto dfs3 = [&](auto &&self, const int v, const int p, const int d) -> void {const int d1 = distList[v];if (d1 - 1 >= d) qsc.push_back({d1 - 1 - d, v});for (const int t : Tree[v]) {if (t == p) continue;if (not isAvailable[t]) continue;self(self, t, v, d + 1);}};dfs3(dfs3, t, centroid, 1);std::sort(qsc.begin(), qsc.end(), [](const auto &a, const auto &b) {return a.first < b.first;});std::queue<int> que;que.push(t);dist1[t] = 1;for (const auto &[a, i] : qsc) {fenTree1.add(i, a);fenTree2.add(i, 1);}int r = 0;while (not que.empty()) {const auto f = que.front();que.pop();while (r != (int)qsc.size() and qsc[r].first - dist1[f] <= 0) {fenTree1.add(qsc[r].second, -qsc[r].first);fenTree2.add(qsc[r].second, -1);++r;}ans[f] -= fenTree1.fold(f + 1, N) - fenTree2.fold(f + 1, N) * dist1[f];for (const int to : Tree[f]) {if (not isAvailable[to]) continue;if (dist1[to] != -1) continue;dist1[to] = dist1[f] + 1;que.push(to);}}while (r != (int)qsc.size()) {fenTree1.add(qsc[r].second, -qsc[r].first);fenTree2.add(qsc[r].second, -1);++r;}std::copy(qsc.begin(), qsc.end(), std::back_inserter(qs));}qs.push_back({distList[centroid] - 1, centroid});std::sort(qs.begin(), qs.end(), [](const auto &a, const auto &b) {return a.first < b.first;});std::queue<int> que;que.push(centroid);dist2[centroid] = 0;for (const auto &[a, i] : qs) {fenTree1.add(i, a);fenTree2.add(i, 1);}int r = 0;while (not que.empty()) {const auto f = que.front();que.pop();while (r != (int)qs.size() and qs[r].first - dist2[f] <= 0) {fenTree1.add(qs[r].second, -qs[r].first);fenTree2.add(qs[r].second, -1);++r;}ans[f] += fenTree1.fold(f + 1, N) - fenTree2.fold(f + 1, N) * dist2[f];for (const int to : Tree[f]) {if (not isAvailable[to]) continue;if (dist2[to] != -1) continue;dist2[to] = dist2[f] + 1;que.push(to);}}while (r != (int)qs.size()) {fenTree1.add(qs[r].second, -qs[r].first);fenTree2.add(qs[r].second, -1);++r;}isAvailable[centroid] = false;for (const int t : Tree[centroid]) {if (not isAvailable[t]) continue;selfD(selfD, t);}};decomposite(decomposite, 0);const auto baseAns = std::accumulate(distList.begin(), distList.end(), 0ll);for (auto &e : ans) e = baseAns - e;return ans;}std::vector<i64> naive_(std::vector<int> X, std::vector<int> Y) {const int N = (int)X.size() + 1;std::vector<std::vector<int>> Tree(N);for (int i = 0; i < N - 1; ++i) {Tree[X[i]].push_back(Y[i]);Tree[Y[i]].push_back(X[i]);}TreeManager sTree(Tree);std::vector<i64> ans(N);for (int i = 0; i < N; ++i) {for (int j = 1; j <= i; ++j) {ans[i] += sTree.dist(j - 1, j);}for (int j = i + 1; j < N; ++j) {const int a = sTree.dist(j - 1, j), b = sTree.dist(i, j) + 1;ans[i] += std::min(a, b);}}return ans;}