QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#121350#4839. Smaller LCAmemset0TL 1906ms91704kbC++208.1kb2023-07-07 23:54:062023-07-07 23:54:07

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 23:54:07]
  • 评测
  • 测评结果:TL
  • 用时:1906ms
  • 内存:91704kb
  • [2023-07-07 23:54:06]
  • 提交

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], d[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 mx, my, 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 <= my; 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);
  }
  inline void addQuery(int x, int y) {
    // cerr << "counter::addQuery " << x << " " << y << endl;
    qry.emplace_back(x, y, qry.size());
  }
  inline int getQuery() {
    // cerr << "counter::getQuery " << ans[tim] << endl;
    return ans[tim++];
  }
  void init() {
    // cerr << "counter::init" << endl;
    tim = 0, nod.clear(), qry.clear();
  }
  void solve() {
    ans.resize(qry.size());
    fill(ans.begin(), ans.end(), 0);
    if (!nod.size() || !qry.size()) return;
    if (nod.size() < 5) {
      for (auto &[xx, yy] : nod) {
        for (auto &[x, y, i] : qry) {
          if (xx <= x && yy <= y) ans[i]++;
        }
      }
      return;
    }
    cerr << "counter::solve " << nod.size() << " " << qry.size() << endl;
    cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
    if (false && nod.size() + qry.size() < n) {
      valx.clear(), valy.clear();
      for (auto &[x, y] : nod) {
        valx.push_back(x);
        valy.push_back(y);
      }
      for (auto &[x, y, i] : qry) {
        valx.push_back(x);
        valy.push_back(y);
      }
      sort(valx.begin(), valx.end());
      sort(valy.begin(), valy.end());
      valx.erase(unique(valx.begin(), valx.end()), valx.end()), mx = valx.size();
      valy.erase(unique(valy.begin(), valy.end()), valy.end()), my = valy.size();
      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 = upper_bound(valx.begin(), valx.end(), x) - valx.begin();
        y = upper_bound(valy.begin(), valy.end(), y) - valy.begin();
        // cerr << "query " << x << " " << y << " " << i << endl;
      }
    } else {
      mx = my = n;
    }
    fill(s, s + my + 1, 0);
    sort(nod.begin(), nod.end());
    sort(qry.begin(), qry.end());
    int i = 0, j = 0;
    for (int x = 1; x <= mx; 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++;
      }
    }
    cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
  }
} counter;
void getroot(int u) {
  siz[u] = 1, mxp[u] = 0;
  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) {
  // cerr << "get query " << u << endl;
  for (int v : G[u])
    if (!vis[v] && v != fa[u]) {
      counter.addQuery(dfn[v] + siz[v] - 1, u - 1);
      counter.addQuery(dfn[v] - 1, u - 1);
      getquery(v);
    }
}
void pushans(int u) {
  // cerr << "push ans " << u << " " << w << " " << tot << endl;
  for (int v : G[u])
    if (!vis[v] && v != fa[u]) {
      int cur = counter.getQuery();
      cur -= counter.getQuery();
      ini::push(u, v, fa[u], cur);
      pushans(v);
    }
}
vector<pair<int, int>> mergeSort(const vector<pair<int, int>> &a, const vector<pair<int, int>> &b) {
  vector<pair<int, int>> c;
  int i = 0, j = 0;
  while (i < a.size() && j < b.size())
    if (a[i].first < b[j].first) {
      c.push_back(a[i++]);
    } else {
      c.push_back(b[j++]);
    }
  while (i < a.size()) c.push_back(a[i++]);
  while (j < b.size()) c.push_back(b[j++]);
  return c;
}
void solve(int u) {
  // cerr << "=== solve " << u << " ===" << endl;
  vis[u] = 1;
  vector<int> ch;
  tot = 1, dfn[u] = siz[u] = 1;
  for (int v : G[u]) {
    if (!vis[v]) ch.push_back(v);
  }
  counter.init();
  for (int k = 0; k < ch.size(); k++) {
    int v = ch[k];
    fa[v] = u;
    d[k].clear(), getnode(v, d[k]);
    siz[u] += siz[v];
  }
  vector<pair<int, int>> dx;
  for (int i = 0; i < ch.size(); i++) {
    sort(d[i].begin(), d[i].end());
    for (int x : d[i])
      if ((long long)x * u < n) {
        counter.addNode(dfn[x], x * u);
      } else {
        break;
      }
    for (int x : d[i]) {
      for (auto &[y, j] : dx)
        if ((long long)x * y < n) {
          counter.addNode(dfn[x], x * y);
          counter.addNode(dfn[y], x * y);
          // fprintf(stderr, "%d %d %d %d\n", x, i, y, j);
          if ((long long)x * y < u) {
            ini::push(u, ch[i], ch[j], 1);
          }
        } else {
          break;
        }
    }
    vector<pair<int, int>> di;
    for (int x : d[i]) di.emplace_back(x, i);
    dx = mergeSort(dx, di);
  }
  qry.clear(), tim = 0;
  for (int v : ch) getquery(v);
  counter.solve();
  for (int v : ch) pushans(v);
  // cerr << tim << " " << qry.size() << endl;
  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;
}

/*
=== solve 5 ===
counter::addNode 3 5
counter::addNode 5 2
counter::addNode 3 2
=== solve 1 ===
counter::addNode 3 4
=== solve 6 ===
=== solve 4 ===
=== solve 3 ===
=== solve 2 ===
21
21
21
20
20
21
time: 0.021


=== solve 5 ===
counter::addNode 3 5
counter::addNode 5 2
counter::addNode 3 2
counter::addNode 6 3
counter::addNode 3 3
counter::solve 5 6
=== solve 1 ===
counter::addNode 3 4
=== solve 6 ===
=== solve 4 ===
=== solve 3 ===
=== solve 2 ===
21
21
21
19
19
21
time: 0.018
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 30312kb

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: 1315ms
memory: 87944kb

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: 1251ms
memory: 91704kb

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: 1316ms
memory: 91556kb

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: 1265ms
memory: 87664kb

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: 1281ms
memory: 89884kb

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: 0
Accepted
time: 1866ms
memory: 89868kb

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:

44999618044
44999147094
44999677093
44999732634
44999460409
44999160790
44999579139
44999467908
44999184681
44999199263
44999231239
44999488195
44999805266
44999547232
44999707240
44999537930
44999505219
44999563833
44999465777
44999426341
44999557653
44999794024
44999548625
44999794023
44999570124
...

result:

ok 300000 numbers

Test #8:

score: 0
Accepted
time: 1872ms
memory: 87524kb

input:

299999
221069 282534
214173 282534
24237 221069
204787 282534
245620 204787
136288 221069
209773 245620
287963 245620
292336 24237
21383 292336
172534 209773
127524 209773
16214 21383
87226 287963
170040 172534
103312 87226
52385 127524
140929 170040
193496 52385
203825 87226
115524 170040
220799 52...

output:

44999572210
44999458670
44998911277
44999184039
44999206776
44999443592
44999417299
44999356502
44999179829
44999237265
44999572056
44999206883
44998942302
44999260955
44998835660
44999452577
44999346141
44999194483
44999380831
44998863337
44998893184
44999520307
44999572157
44999173592
44999110483
...

result:

ok 299999 numbers

Test #9:

score: 0
Accepted
time: 1851ms
memory: 88308kb

input:

300000
8889 36706
157543 8889
104012 8889
62314 157543
242859 36706
149378 8889
10456 157543
29565 104012
131101 149378
22513 131101
90461 22513
40078 131101
141748 10456
72882 22513
176272 22513
90154 141748
215195 90154
43336 40078
296478 90154
128801 90154
149034 128801
102954 149034
254677 29647...

output:

44999724123
44999887080
44999879556
44999518077
44999609913
44999556275
44999588000
44999593838
44999680913
44999380889
44999880288
44999657021
44999383706
44999144202
44999478288
44999199032
44999614075
44999790343
44999766790
44999445094
44999424718
44999260077
44999887302
44999847443
44999676358
...

result:

ok 300000 numbers

Test #10:

score: 0
Accepted
time: 1904ms
memory: 89740kb

input:

299998
29430 279377
87865 279377
33400 87865
149559 33400
218448 149559
274422 87865
62550 149559
215553 274422
239913 274422
107224 149559
289982 218448
256498 239913
143232 239913
103543 289982
90558 107224
254844 143232
7345 90558
139410 143232
171957 90558
85463 139410
207261 171957
128676 13941...

output:

44998919397
44998530568
44998745272
44999059683
44999013065
44999181214
44999129502
44999154742
44999172744
44998691167
44998858765
44999070146
44998807013
44998859372
44998761740
44999120708
44998877194
44998808804
44998912953
44998550644
44999009720
44998818725
44999061235
44998695918
44999085009
...

result:

ok 299998 numbers

Test #11:

score: 0
Accepted
time: 1906ms
memory: 90372kb

input:

299999
279808 219366
64566 279808
294679 64566
192527 294679
290866 294679
282142 64566
112420 290866
29858 290866
269073 112420
19694 112420
66844 19694
42940 112420
142231 112420
58837 142231
295419 58837
9002 19694
4808 142231
7272 9002
30675 4808
62872 30675
81916 7272
260542 62872
146224 62872
...

output:

44999374155
44999307472
44999179996
44999188269
44999102614
44999300805
44998993219
44999018542
44999252456
44999480338
44999203231
44998930625
44999347959
44999487732
44999529114
44998903631
44999333440
44999238520
44999388913
44999277968
44999288307
44998958543
44999163087
44999009462
44999226099
...

result:

ok 299999 numbers

Test #12:

score: -100
Time Limit Exceeded

input:

299998
150616 76335
88273 150616
206635 76335
200072 206635
38950 150616
298642 206635
179779 200072
246700 38950
231698 88273
202098 76335
105468 38950
265562 38950
173901 38950
211307 200072
159253 88273
131738 150616
17278 76335
103492 76335
173877 206635
10117 38950
294264 38950
9644 206635
2619...

output:


result: