結果
| 問題 | No.2491 Pochi and A Warp Machine |
| ユーザー |
 square1001
|
| 提出日時 | 2023-09-29 23:19:35 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,628 ms / 3,000 ms |
| コード長 | 6,793 bytes |
| コンパイル時間 | 2,677 ms |
| コンパイル使用メモリ | 231,540 KB |
| 最終ジャッジ日時 | 2025-02-17 03:35:35 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int INF = 1012345678;struct edge {int va, vb;};struct state {int depth, current, bottom;};string to_string(const vector<int>& arr) {string res = "[";for (int i = 0; i < arr.size(); i++) {if (i != 0) {res += ", ";}res += to_string(arr[i]);}res += "]";return res;}class fenwicktree {private:int n;vector<int> comp;vector<long long> val;public:fenwicktree() : n(0), comp(vector<int>()), val(vector<long long>()) {}fenwicktree(const vector<int>& comp_) : n(comp_.size()), comp(comp_), val(vector<long long>(comp_.size() + 1)) {}void add(int pos, long long x) {pos = lower_bound(comp.begin(), comp.end(), pos) - comp.begin();for (int i = pos + 1; i <= n; i += i & (-i)) {val[i] += x;}}long long rangesum(int r) {r = lower_bound(comp.begin(), comp.end(), r) - comp.begin();long long ans = 0;for (int i = r; i >= 1; i -= i & (-i)) {ans += val[i];}return ans;}};void solve(int N, const vector<int>& P, const vector<edge>& E, const vector<int>& dlist, vector<long long>& ans) {// step #1. make graphvector<vector<int> > G(N);for (edge e : E) {G[e.va].push_back(e.vb);G[e.vb].push_back(e.va);}// step #2. find centroidint root = -1;vector<int> subsize(N, 1);auto find_centroid = [&](auto& self, int pos, int pre) -> void {bool flag = true;for (int i : G[pos]) {if (i != pre) {self(self, i, pos);subsize[pos] += subsize[i];if (subsize[i] * 2 > N) {flag = false;}}}if (flag && subsize[pos] * 2 >= N) {root = pos;}};find_centroid(find_centroid, 0, -1);// step #3. build treevector<int> depth(N);vector<int> comp(N, -1);vector<vector<int> > child(N);auto build_tree = [&](auto& self, int pos, int pre) -> void {for (int i : G[pos]) {if (i != pre) {comp[i] = comp[pos];depth[i] = depth[pos] + 1;child[pos].push_back(i);self(self, i, pos);}}};int K = G[root].size();child[root] = G[root];for (int i = 0; i < K; i++) {comp[G[root][i]] = i;depth[G[root][i]] = 1;build_tree(build_tree, G[root][i], root);}// step #5. calculate answer passing rootvector<int> ord(N);for (int i = 0; i < N; i++) {ord[i] = i;}sort(ord.begin(), ord.end(), [&](int va, int vb) {return P[va] > P[vb];});// cerr << "N = " << N << endl;// cerr << "centroid = " << root << endl;vector<int> diff(N);for (int i = 0; i < N; i++) {int idx = P[i];diff[i] = (idx != 0 ? dlist[idx - 1] : 0) - depth[i] - 1;}int Z = dlist.size() + 1;vector<vector<int> > diffcomp(K + 1);for (int i = 0; i < N; i++) {if (diff[i] >= 0) {diffcomp[K].push_back(Z - diff[i] - 1);if (i != root) {diffcomp[comp[i]].push_back(Z - diff[i] - 1);}}}for (int i = 0; i <= K; i++) {sort(diffcomp[i].begin(), diffcomp[i].end());diffcomp[i].erase(unique(diffcomp[i].begin(), diffcomp[i].end()), diffcomp[i].end());}vector<fenwicktree> bit0(K + 1);vector<fenwicktree> bit1(K + 1);for (int i = 0; i <= K; i++) {bit0[i] = fenwicktree(diffcomp[i]);bit1[i] = fenwicktree(diffcomp[i]);}for (int i : ord) {int idx = P[i];// cost1: dlist[target_idx - 1]// cost2: 1 + depth[i] + depth[target]// if dlist[target_idx - 1] - depth[target] - 1 >= depth[i], profitlong long profit = 0;profit += bit1[K].rangesum(Z - depth[i]);profit -= bit0[K].rangesum(Z - depth[i]) * depth[i];if (i != root) {profit -= bit1[comp[i]].rangesum(Z - depth[i]);profit += bit0[comp[i]].rangesum(Z - depth[i]) * depth[i];}ans[idx] -= profit;int diff = (idx != 0 ? dlist[idx - 1] : 0) - depth[i] - 1;// cerr << "i = " << i << ": idx = " << idx << ", profit = " << profit << ", diff = " << diff << endl;if (diff >= 0) {bit0[K].add(Z - diff - 1, 1);bit1[K].add(Z - diff - 1, diff);if (i != root) {bit0[comp[i]].add(Z - diff - 1, 1);bit1[comp[i]].add(Z - diff - 1, diff);}}}// step #6. divide into subproblemsvector<vector<int> > subcomp(K);for (int i = 0; i < N; i++) {if (i != root) {subcomp[comp[i]].push_back(i);}}vector<vector<int> > subp(K);vector<vector<edge> > sube(K);for (int i = 0; i < K; i++) {subp[i].resize(subcomp[i].size());for (int j = 0; j < subcomp[i].size(); j++) {subp[i][j] = P[subcomp[i][j]];}}for (int i = 0; i < N - 1; i++) {if (comp[E[i].va] == comp[E[i].vb]) {int id = comp[E[i].va];int nva = lower_bound(subcomp[id].begin(), subcomp[id].end(), E[i].va) - subcomp[id].begin();int nvb = lower_bound(subcomp[id].begin(), subcomp[id].end(), E[i].vb) - subcomp[id].begin();sube[id].push_back(edge{nva, nvb});}}for (int i = 0; i < K; i++) {solve(subcomp[i].size(), subp[i], sube[i], dlist, ans);}}vector<int> distances(int N, const vector<edge>& E, const vector<int>& S, const vector<int>& T) {vector<vector<int> > G(N);for (edge e : E) {G[e.va].push_back(e.vb);G[e.vb].push_back(e.va);}vector<int> par(N);vector<int> depth(N);auto build_tree = [&](auto& self, int pos, int pre) -> void {for (int i : G[pos]) {if (i != pre) {par[i] = pos;depth[i] = depth[pos] + 1;self(self, i, pos);}}};build_tree(build_tree, 0, -1);int bits = (N >= 3 ? 32 - __builtin_clz(N - 1) : N);vector<vector<int> > spar(bits);spar[0] = par;spar[0][0] = 0;for (int i = 1; i < bits; i++) {spar[i].resize(N);for (int j = 0; j < N; j++) {spar[i][j] = spar[i - 1][spar[i - 1][j]];}}auto lca = [&](int va, int vb) {if (depth[va] < depth[vb]) {swap(va, vb);}int d = depth[va] - depth[vb];for (int i = 0; i < bits; i++) {if ((d >> i) & 1) {va = spar[i][va];}}if (va == vb) {return va;}for (int i = bits - 1; i >= 0; i--) {if (spar[i][va] != spar[i][vb]) {va = spar[i][va];vb = spar[i][vb];}}return spar[0][va];};vector<int> ans(S.size());for (int i = 0; i < S.size(); i++) {ans[i] = depth[S[i]] + depth[T[i]] - depth[lca(S[i], T[i])] * 2;// cerr << "N = " << N << ", S = " << S[i] << ", T = " << T[i] << ", ans = " << ans[i] << endl;}return ans;}int main() {cin.tie(0);ios::sync_with_stdio(false);int N;cin >> N;vector<edge> E(N - 1);for (int i = 0; i < N - 1; i++) {cin >> E[i].va >> E[i].vb;E[i].va -= 1;E[i].vb -= 1;}vector<int> P(N), A(N - 1), B(N - 1);for (int i = 0; i < N; i++) {P[i] = i;if (i != N - 1) {A[i] = i;B[i] = i + 1;}}vector<int> D = distances(N, E, A, B);long long dsum = 0;for (int i = 0; i < N - 1; i++) {dsum += D[i];}vector<long long> ans(N, dsum);solve(N, P, E, D, ans);for (int i = 0; i < N; i++) {cout << ans[i] << '\n';}return 0;}