QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#121315#4839. Smaller LCAmemset0TL 3675ms176944kbC++207.1kb2023-07-07 22:31:252023-07-07 22:31:26

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 22:31:26]
  • 评测
  • 测评结果:TL
  • 用时:3675ms
  • 内存:176944kb
  • [2023-07-07 22:31:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
int n, rt, all, tot, tim, fa[N], siz[N], mxp[N], dfn[N], ans[N];
bool vis[N];
vector<int> G[N];
vector<tuple<int, int, int, int>> qry;
namespace ini {
int tot, fa[N], dfn[N], siz[N];
long long sum, pre[N];
void dfs(int u) {
  dfn[u] = ++tot;
  siz[u] = 1;
  for (int v : G[u])
    if (v != fa[u]) {
      fa[v] = u;
      dfs(v);
      siz[u] += siz[v];
    }
}
void push(int u, int x) {
  pre[dfn[u]] += x;
  pre[dfn[u] + 1] -= x;
}
void push(int u, int v, int x) {
  if (v == fa[u]) {
    pre[0] += x;
    pre[dfn[u]] -= x;
    pre[dfn[u] + siz[u]] += x;
  } else {
    pre[dfn[v]] += x;
    pre[dfn[v] + siz[v]] -= x;
  }
}
inline void push(int u, int v, int w, int x) {
  // fprintf(stderr, "push %d %d %d : %d\n", u, v, w, x);
  pre[0] += x;
  push(u, v, -x);
  // for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
  push(u, w, -x);
  // for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
}
void init() {
  dfs(1);
  // for (int i = 1; i <= n; i++) cerr << dfn[i] << " \n"[i == n];
  // for (int i = 1; i <= n; i++) cerr << siz[i] << " \n"[i == n];
}
void solve() {
  // for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
  for (int i = 1; i <= n; i++) pre[i] += pre[i - 1];
  // for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
  for (int i = 1; i <= n; i++) ans[i] += pre[dfn[i]];
}
} // namespace ini
struct CountNode {
  int n, tim, s[N << 1];
  vector<int> ans, valx, valy;
  vector<pair<int, int>> nod;
  vector<tuple<int, int, int>> qry;
  inline void add(int k) {
    for (; k <= n; k += k & -k) s[k]++;
  }
  inline void ask(int k, int &x) {
    for (; k; k -= k & -k) x += s[k];
  }
  inline void addNode(int x, int y) {
    // cerr << "counter::addNode " << x << " " << y << endl;
    nod.emplace_back(x, y);
    valx.push_back(x), valy.push_back(y);
  }
  inline void addQuery(int x, int y) {
    // cerr << "counter::addQuery " << x << " " << y << endl;
    qry.emplace_back(x, y, qry.size());
    valx.push_back(x), valy.push_back(y);
  }
  inline int getQuery() {
    // cerr << "counter::getQuery " << ans[tim] << endl;
    return ans[tim++];
  }
  void init() {
    // cerr << "counter::init" << endl;
    tim = 0, nod.clear(), qry.clear(), valx.clear(), valy.clear();
  }
  void solve() {
    // cerr << "counter::solve" << endl;
    ans.resize(qry.size());
    fill(ans.begin(), ans.end(), 0);
    if (!nod.size()) return;
    sort(valx.begin(), valx.end());
    sort(valy.begin(), valy.end());
    valx.erase(unique(valx.begin(), valx.end()), valx.end());
    valy.erase(unique(valy.begin(), valy.end()), valy.end());
    n = valy.size();
    fill(s, s + n + 1, 0);
    for (auto &[x, y] : nod) {
      x = lower_bound(valx.begin(), valx.end(), x) - valx.begin() + 1;
      y = lower_bound(valy.begin(), valy.end(), y) - valy.begin() + 1;
      // cerr << "node " << x << " " << y << endl;
    }
    for (auto &[x, y, i] : qry) {
      x = lower_bound(valx.begin(), valx.end(), x) - valx.begin() + 1;
      y = lower_bound(valy.begin(), valy.end(), y) - valy.begin() + 1;
      // cerr << "query " << x << " " << y << " " << i << endl;
    }
    sort(nod.begin(), nod.end());
    sort(qry.begin(), qry.end());
    int i = 0, j = 0;
    for (int x = 1; x <= valx.size(); x++) {
      while (i < nod.size() && nod[i].first == x) {
        add(nod[i].second), i++;
      }
      while (j < qry.size() && get<0>(qry[j]) == x) {
        ask(get<1>(qry[j]), ans[get<2>(qry[j])]), j++;
      }
    }
  }
} counter;
void getroot(int u) {
  siz[u] = 1;
  for (int v : G[u])
    if (!vis[v] && v != fa[u]) {
      fa[v] = u;
      getroot(v);
      siz[u] += siz[v];
      mxp[u] = max(mxp[u], siz[v]);
    }
  mxp[u] = max(mxp[u], all - siz[u]);
  if (!rt || mxp[u] < mxp[rt]) rt = u;
}
void getnode(int u, vector<int> &cur) {
  // cerr << "get node " << u << endl;
  cur.push_back(u);
  dfn[u] = ++tot, siz[u] = 1;
  for (int v : G[u]) {
    if (!vis[v] && v != fa[u]) {
      fa[v] = u;
      getnode(v, cur);
      siz[u] += siz[v];
    }
  }
}
void getquery(int u, int sub) {
  // cerr << "get query " << u << endl;
  // qry.emplace_back(dfn[u] + siz[u] - 1, u - 1, sub, 0); // plus this ans
  // qry.emplace_back(dfn[u] - 1, u - 1, sub, 0);          // minus this ans
  for (int v : G[u])
    if (!vis[v] && v != fa[u]) {
      qry.emplace_back(dfn[v] + siz[v] - 1, u - 1, sub, 0); // plus this ans
      qry.emplace_back(dfn[v] - 1, u - 1, sub, 0);          // minus this ans
      getquery(v, sub);
    }
}
inline int getresult() {
  int res = get<3>(qry[tim++]);
  res -= get<3>(qry[tim++]);
  return res;
}
void pushans(int u) {
  // cerr << "push ans " << u << " " << w << " " << tot << endl;
  for (int v : G[u])
    if (!vis[v] && v != fa[u]) {
      int cur = getresult();
      ini::push(u, v, fa[u], cur);
      pushans(v);
    }
}
void solve(int u) {
  // cerr << "=== solve " << u << " ===" << endl;
  vis[u] = 1;
  vector<int> ch;
  set<pair<int, int>> pre = {{u, 0}};
  map<int, vector<int>> d;
  map<int, vector<pair<int, int>>> p;
  tot = 1, dfn[u] = siz[u] = 1;
  for (int v : G[u]) {
    if (!vis[v]) ch.push_back(v);
  }
  for (int v : ch) {
    fa[v] = u;
    d[v] = {}, getnode(v, d[v]);
    siz[u] += siz[v];
    p[v] = {};
    for (int x : d[v])
      for (auto &[y, w] : pre) {
        if ((long long)x * y < n) {
          p[v].emplace_back(x, y);
          if (w) p[w].emplace_back(y, x);
          if (u > (long long)x * y) {
            ini::push(u, v, w, 1);
          }
        } else {
          break;
        }
      }
    for (int x : d[v]) pre.insert(make_pair(x, v));
  }
  qry.clear(), tim = 0;
  for (int k = 0; k < ch.size(); k++) getquery(ch[k], k);
  counter.init();
  for (int v : ch)
    for (auto &[x, y] : p[v]) {
      counter.addNode(dfn[x], x * y);
    }
  for (int i = 0, k = 0; k < ch.size(); k++) {
    while (i < qry.size() && get<2>(qry[i]) < k) ++i;
    for (int j = i; j < qry.size() && get<2>(qry[j]) == k; j++) {
      counter.addQuery(get<0>(qry[j]), get<1>(qry[j]));
    }
  }
  counter.solve();
  for (int i = 0, k = 0; k < ch.size(); k++) {
    while (i < qry.size() && get<2>(qry[i]) < k) ++i;
    for (int j = i; j < qry.size() && get<2>(qry[j]) == k; j++) {
      get<3>(qry[j]) += counter.getQuery();
    }
    pushans(ch[k]);
  }
  for (int v : ch) {
    rt = 0, all = siz[v], getroot(v), solve(rt);
  }
}
int main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
  // freopen("2.in", "r", stdin);
  // freopen("2.out", "w", stdout);
#endif
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int u, v, i = 1; i < n; i++) {
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  ini::init();
  rt = 0, all = n, getroot(1), solve(rt);
  ini::solve();
  long long tot = (long long)n * (n - 1) / 2 + n;
  // for (int i = 1; i <= n; i++) cerr << ans[i] << " \n"[i == n];
  for (int i = 1; i <= n; i++) cout << (tot - ans[i]) << '\n';
  cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 22328kb

input:

5
1 2
4 2
2 5
3 5

output:

15
15
15
15
14

result:

ok 5 number(s): "15 15 15 15 14"

Test #2:

score: 0
Accepted
time: 3675ms
memory: 176944kb

input:

300000
40632 143306
32259 40632
225153 143306
269774 225153
289668 40632
191636 269774
85717 191636
58564 191636
156509 143306
289939 40632
247103 269774
40257 40632
98149 289668
142277 143306
291616 40257
46813 225153
56324 143306
277154 142277
53903 289668
114266 32259
152231 58564
241151 152231
4...

output:

44999437117
44999604051
44999615557
44999614574
44999052534
44999484860
44999371316
44999125588
44999026878
44999118903
44999600090
44999126307
44999249359
44999307961
44999422135
44999360213
44999109672
44999283107
44999293969
44999113471
44999549862
44999278828
44999353626
44999122409
44999352565
...

result:

ok 300000 numbers

Test #3:

score: 0
Accepted
time: 3320ms
memory: 166552kb

input:

299999
97687 248627
80337 97687
77032 80337
92616 80337
106631 248627
248726 77032
176093 92616
73262 248726
233147 80337
39942 248726
15921 176093
188366 248627
31058 80337
239076 73262
44766 233147
10344 176093
192127 233147
109285 80337
6814 176093
239926 97687
204083 77032
252211 15921
5158 7703...

output:

44999344660
44999363522
44999206495
44999093451
44999362732
44999276207
44999352410
44999343961
44999149170
44999277616
44999158043
44999332131
44999288440
44999317886
44999301651
44999266803
44999346932
44999241092
44999298075
44999129430
44999277318
44999272323
44999209973
44999271917
44999269931
...

result:

ok 299999 numbers

Test #4:

score: 0
Accepted
time: 3311ms
memory: 168728kb

input:

300000
282498 119808
46316 119808
58818 119808
179940 119808
6601 282498
16229 46316
25007 58818
180795 16229
83945 179940
246574 179940
268478 179940
134193 246574
164637 6601
78275 83945
241804 119808
177735 6601
225133 134193
188943 179940
36121 188943
148019 164637
223449 180795
41835 188943
237...

output:

44999540514
44999412634
44999309802
44999471134
44999211366
44999458009
44999479974
44999281366
44999372403
44999448719
44999365824
44999443217
44999455734
44999482977
44999585712
44999540082
44999475151
44999453573
44999399100
44999346705
44999372230
44999256996
44999368064
44999452600
44999473178
...

result:

ok 300000 numbers

Test #5:

score: 0
Accepted
time: 3391ms
memory: 165044kb

input:

299999
173205 142232
104374 142232
39513 104374
67867 104374
42519 173205
145713 39513
190264 104374
240190 67867
220708 240190
237545 67867
211015 220708
73889 39513
126319 220708
38274 67867
257538 240190
260471 237545
44453 142232
24527 142232
23487 173205
174569 173205
158023 173205
100347 42519...

output:

44999145790
44999091319
44999049858
44999174810
44998980768
44999252786
44999144473
44998983973
44998953014
44999259775
44998949495
44999055625
44998909201
44998956878
44999261370
44998927703
44999167393
44999140464
44998905939
44998940216
44998919447
44999239170
44999100182
44998941726
44999273329
...

result:

ok 299999 numbers

Test #6:

score: 0
Accepted
time: 3594ms
memory: 171068kb

input:

299999
144140 64463
84381 64463
275996 144140
144612 144140
22940 275996
97432 275996
258170 64463
268975 84381
113121 268975
74024 258170
162810 275996
222898 74024
218308 22940
294515 64463
4344 218308
287764 74024
73585 97432
116481 287764
204008 144140
125526 73585
133816 294515
31053 258170
107...

output:

44999005167
44999209294
44998941343
44998935023
44999171993
44999086771
44999206524
44999091272
44998923732
44999092407
44999090745
44998910337
44998836857
44999087877
44999105320
44998879519
44998983003
44998798532
44998760921
44999084330
44999064280
44999054760
44999103030
44999130090
44999053488
...

result:

ok 299999 numbers

Test #7:

score: -100
Time Limit Exceeded

input:

300000
17050 75638
59628 17050
250487 75638
222372 17050
83877 75638
252612 59628
223823 83877
71675 252612
264309 223823
56862 222372
250608 83877
112630 223823
122103 250608
148130 56862
32428 112630
181607 56862
230036 148130
99321 230036
211188 181607
272235 148130
57324 272235
260876 272235
191...

output:


result: