QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#152223#439. 命运hos_lyric100 ✓1193ms724544kbC++148.9kb2023-08-27 19:29:102023-08-27 19:29:12

Judging History

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

  • [2023-08-27 19:29:12]
  • 评测
  • 测评结果:100
  • 用时:1193ms
  • 内存:724544kb
  • [2023-08-27 19:29:10]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;


struct Node {
  int l, r;
  Mint same;
  // lazy: t -> p t + q
  Mint p, q;
  Node() : l(-1), r(-1), p(1), q(0) {}
  void mul(Mint val) {
    same *= val;
    p *= val;
    q *= val;
  }
  void add(Mint val) {
    same += val;
    q += val;
  }
};
vector<Node> nodes;
int newNode() {
  const int u = nodes.size();
  nodes.emplace_back();
  return u;
}
void push(int u) {
  const int l = nodes[u].l;
  const int r = nodes[u].r;
  Mint &p = nodes[u].p;
  Mint &q = nodes[u].q;
  if (!(p == 1 && q == 0)) {
    if (~l) {
      nodes[l].mul(p);
      nodes[l].add(q);
    }
    if (~r) {
      nodes[r].mul(p);
      nodes[r].add(q);
    }
    p = 1;
    q = 0;
  }
}
void pull(int u, int l, int r) {
  assert(~l || ~r);
  nodes[u].l = l;
  nodes[u].r = r;
}
int merge(int u, int v) {
// cerr<<"  merge "<<u<<" "<<v<<endl;
  if (!~u) return v;
  if (!~v) return u;
  if (!~nodes[u].l && !~nodes[u].r) {
    nodes[v].mul(nodes[u].same);
    return v;
  }
  if (!~nodes[v].l && !~nodes[v].r) {
    nodes[u].mul(nodes[v].same);
    return u;
  }
  push(u);
  push(v);
  const int l = merge(nodes[u].l, nodes[v].l);
  const int r = merge(nodes[u].r, nodes[v].r);
  pull(u, l, r);
  return u;
}
int segN;
int build(int L, int R, int a, int b, Mint valOut, Mint valIn) {
  if (b <= L || R <= a) {
    const int u = newNode();
    nodes[u].same = valOut;
    return u;
  }
  if (a <= L && R <= b) {
    const int u = newNode();
    nodes[u].same = valIn;
    return u;
  }
  const int Mid = (L + R) >> 1;
  const int l = build(L, Mid, a, b, valOut, valIn);
  const int r = build(Mid, R, a, b, valOut, valIn);
  const int u = newNode();
  pull(u, l, r);
  return u;
}
int filter(int L, int R, int u, int a, int b) {
  if (b <= L || R <= a) {
    nodes[u].mul(0);
    return u;
  }
  if (a <= L && R <= b) {
    return u;
  }
  const int Mid = (L + R) >> 1;
  push(u);
  if (!~nodes[u].l && !~nodes[u].r) {
    const int l = newNode();
    const int r = newNode();
    nodes[u].l = l;
    nodes[u].r = r;
    nodes[l].same = nodes[r].same = nodes[u].same;
  }
  const int l = nodes[u].l;
  const int r = nodes[u].r;
  filter(L, Mid, l, a, b);
  filter(Mid, R, r, a, b);
  pull(u, l, r);
  return u;
}
void add(int L, int R, int u, int a, int b, Mint val) {
  if (!~u) return;
  if (b <= L || R <= a) return;
  if (a <= L && R <= b) {
    nodes[u].add(val);
    return;
  }
  const int Mid = (L + R) >> 1;
  const int l = nodes[u].l;
  const int r = nodes[u].r;
  push(u);
  add(L, Mid, l, a, b, val);
  add(Mid, R, r, a, b, val);
  pull(u, l, r);
}
Mint get(int L, int R, int u, int a) {
  assert(~u);
  const int l = nodes[u].l;
  const int r = nodes[u].r;
  if (!~l && !~r) return nodes[u].same;
  push(u);
  const int Mid = (L + R) >> 1;
  if (a < Mid) {
    return get(L, Mid, l, a);
  } else {
    return get(Mid, R, r, a);
  }
}


int N;
vector<int> A, B;
int M;
vector<int> S, T;

vector<vector<int>> graph;
vector<int> dep;
void dfs(int u, int p) {
  dep[u] = (~p) ? (dep[p] + 1) : 0;
  auto it = find(graph[u].begin(), graph[u].end(), p);
  if (it != graph[u].end()) {
    graph[u].erase(it);
  }
  for (const int v : graph[u]) {
    dfs(v, u);
  }
}

vector<int> maxDs;

int solve(int u) {
  const int d = dep[u];
  int ret = build(0, segN, 0, d + 1, 0, 1);
  for (const int v : graph[u]) {
    int res = solve(v);
    const Mint tail = get(0, segN, res, d + 1);
// cerr<<"  "<<u<<" "<<v<<": tail = "<<tail<<"; ";for(int x=0;x<=d+1;++x)cerr<<get(0,segN,res,x)<<" ";cerr<<endl;
    res = filter(0, segN, res, 0, d + 1);
// cerr<<"  "<<u<<" "<<v<<": tail = "<<tail<<"; ";for(int x=0;x<=d+1;++x)cerr<<get(0,segN,res,x)<<" ";cerr<<endl;
    add(0, segN, res, 0, d + 1, tail);
// cerr<<"  "<<u<<" "<<v<<": tail = "<<tail<<"; ";for(int x=0;x<=d+1;++x)cerr<<get(0,segN,res,x)<<" ";cerr<<endl;
    ret = merge(ret, res);
  }
// cerr<<u<<": ";for(int x=0;x<=d;++x)cerr<<get(0,segN,ret,x)<<" ";cerr<<endl;
  if (~maxDs[u]) {
    ret = filter(0, segN, ret, maxDs[u] + 1, d + 1);
// cerr<<u<<": ";for(int x=0;x<=d;++x)cerr<<get(0,segN,ret,x)<<" ";cerr<<endl;
  }
  return ret;
}

int main() {
  for (; ~scanf("%d", &N); ) {
    A.resize(N - 1);
    B.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    scanf("%d", &M);
    S.resize(M);
    T.resize(M);
    for (int j = 0; j < M; ++j) {
      scanf("%d%d", &S[j], &T[j]);
      --S[j];
      --T[j];
    }
cerr<<"N = "<<N<<", M = "<<M<<endl;
    
    graph.assign(N, {});
    for (int i = 0; i < N - 1; ++i) {
      graph[A[i]].push_back(B[i]);
      graph[B[i]].push_back(A[i]);
    }
    dep.assign(N, -1);
    dfs(0, -1);
    
    const int maxDep = *max_element(dep.begin(), dep.end());
    for (segN = 1; segN < maxDep + 1; segN <<= 1) {}
    nodes.clear();
    
    maxDs.assign(N, -1);
    for (int j = 0; j < M; ++j) {
      chmax(maxDs[T[j]], dep[S[j]]);
    }
// cerr<<"maxDs = "<<maxDs<<endl;
    
    const int res = solve(0);
    const Mint ans = get(0, segN, res, 0);
    printf("%u\n", ans.x);
cerr<<"|nodes| = "<<nodes.size()<<endl;
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 4
Accepted
time: 1ms
memory: 3692kb

input:

6
2 3
6 5
6 4
6 1
2 4
7
1 2
4 2
1 6
2 3
6 5
6 2
6 2

output:

2

result:

ok answer is '2'

Test #2:

score: 4
Accepted
time: 1ms
memory: 3704kb

input:

7
6 4
3 6
3 2
3 7
1 4
5 7
9
1 2
1 5
1 7
1 5
1 4
6 2
3 7
4 3
3 2

output:

6

result:

ok answer is '6'

Test #3:

score: 4
Accepted
time: 1ms
memory: 3672kb

input:

8
6 8
7 6
6 1
6 5
2 8
4 6
6 3
8
6 7
6 8
1 6
6 8
8 2
6 7
1 5
1 6

output:

8

result:

ok answer is '8'

Test #4:

score: 4
Accepted
time: 1ms
memory: 3672kb

input:

9
6 4
1 7
1 3
4 8
2 7
5 1
1 4
9 4
10
1 5
1 9
4 9
1 5
1 4
1 8
1 5
1 2
1 2
1 2

output:

24

result:

ok answer is '24'

Test #5:

score: 4
Accepted
time: 2ms
memory: 3860kb

input:

497
255 412
294 262
337 292
138 17
74 260
134 344
453 364
114 289
50 280
360 179
51 433
497 438
490 422
99 119
345 318
259 396
298 272
431 37
38 15
101 213
230 195
193 33
126 307
106 170
24 200
245 367
266 75
275 67
405 432
220 331
411 441
452 479
219 16
410 245
219 312
476 424
104 356
144 230
251 2...

output:

913693353

result:

ok answer is '913693353'

Test #6:

score: 4
Accepted
time: 4ms
memory: 10916kb

input:

10000
2286 4570
6005 8498
6796 7409
8543 5599
5964 3049
9689 64
555 8795
8719 1929
5814 6317
7104 2223
5537 4410
150 1311
9975 2583
8069 5198
6516 9798
7906 2340
9867 3843
1566 6050
4261 1981
6603 9122
7172 6996
9675 5124
6680 9947
920 1437
6693 4264
4977 7255
3707 2622
9914 4090
588 3714
147 7574
8...

output:

741099208

result:

ok answer is '741099208'

Test #7:

score: 4
Accepted
time: 124ms
memory: 95792kb

input:

99999
24827 62592
58601 32988
9374 5313
16621 75518
13429 72361
72162 10410
19352 43426
50088 85249
60117 54428
45780 95257
71828 69234
45367 69122
8537 31711
19060 14175
49101 29413
77638 37540
14341 97505
86792 56691
24399 74996
48465 6197
84803 31855
79897 68879
43215 30590
32130 9225
41151 5727
...

output:

298377224

result:

ok answer is '298377224'

Test #8:

score: 4
Accepted
time: 842ms
memory: 703724kb

input:

500000
481001 130369
33906 415753
490524 96079
164735 455776
70736 279997
378857 446203
146479 379023
277575 479123
279016 452847
157934 276420
365178 355559
92278 334178
384516 170203
53281 287053
91013 116371
66198 157826
439312 51593
299436 230757
87865 296922
14619 361816
196065 266068
333188 40...

output:

620543783

result:

ok answer is '620543783'

Test #9:

score: 4
Accepted
time: 142ms
memory: 94512kb

input:

99997
12420 85497
96299 96503
91359 61879
73963 53821
8421 57985
20625 76112
7710 49712
37822 48930
73283 21602
95544 63863
48109 71430
71156 13272
94319 85892
44636 21771
13012 32434
25568 67705
2402 72273
45184 77931
47042 90239
24095 8125
28880 6901
53229 34081
99484 60358
11889 94257
40320 63099...

output:

76263105

result:

ok answer is '76263105'

Test #10:

score: 4
Accepted
time: 867ms
memory: 704448kb

input:

499997
30888 482221
413340 184626
407235 423912
444162 164665
292046 377512
92865 497459
295659 434257
373183 130281
274974 165820
417090 329358
457165 135108
364466 306280
481928 272283
203252 229766
184132 104900
1319 197293
95369 415252
423790 88530
453001 268063
55065 23949
434123 184247
239979 ...

output:

495702396

result:

ok answer is '495702396'

Test #11:

score: 4
Accepted
time: 2ms
memory: 3792kb

input:

598
495 238
121 55
369 328
139 276
230 262
309 232
357 183
521 350
177 193
557 336
214 12
285 13
137 36
353 208
81 470
361 583
226 418
88 364
280 252
428 338
216 142
35 584
62 326
27 594
151 6
425 339
159 464
209 224
598 294
312 90
466 185
108 374
253 379
524 289
389 458
78 446
332 319
511 21
468 16...

output:

422402046

result:

ok answer is '422402046'

Test #12:

score: 4
Accepted
time: 2ms
memory: 4056kb

input:

999
634 560
72 10
17 369
466 932
424 205
200 457
53 37
252 64
866 450
669 985
607 667
30 584
733 678
666 10
450 328
375 924
283 189
948 327
665 700
831 267
315 305
117 352
201 929
704 672
10 51
450 868
966 978
540 76
275 15
35 398
405 109
395 92
327 146
411 135
10 972
10 917
623 600
719 123
208 370
...

output:

426197544

result:

ok answer is '426197544'

Test #13:

score: 4
Accepted
time: 50ms
memory: 8744kb

input:

1998
1129 982
64 915
984 1123
606 220
1624 1776
401 1840
159 370
1733 1699
753 317
559 1096
1443 152
1678 682
1033 1153
1745 350
1908 325
618 454
194 1195
786 1254
950 912
784 1582
333 910
32 279
1818 823
1426 990
1863 1182
1428 1526
1113 373
884 609
1113 270
1094 391
405 1440
784 959
998 1509
205 1...

output:

259778043

result:

ok answer is '259778043'

Test #14:

score: 4
Accepted
time: 61ms
memory: 8632kb

input:

1999
1039 956
987 1079
113 930
1411 1611
99 1121
115 1379
1811 835
855 44
78 378
833 1317
1642 841
1012 1411
1504 841
588 851
1565 1811
1411 1687
361 1712
1538 1411
819 584
477 1146
1014 1268
1956 366
430 287
1043 1294
910 1413
676 16
1024 1027
1915 841
1411 178
1399 1185
1937 158
1397 841
68 249
13...

output:

719079531

result:

ok answer is '719079531'

Test #15:

score: 4
Accepted
time: 818ms
memory: 715748kb

input:

499996
166429 374240
458250 186205
337525 397040
105532 121824
323632 293915
266697 417228
180442 297190
79265 219324
80328 16227
130791 321970
91028 57527
42303 425087
297432 223699
311644 18598
155816 2585
280416 329400
38048 413818
353672 18723
460086 20894
376884 401233
273015 96291
64286 98896
...

output:

440462992

result:

ok answer is '440462992'

Test #16:

score: 4
Accepted
time: 908ms
memory: 721288kb

input:

499999
429752 39010
87476 462988
436786 265632
313093 371847
150379 79799
292525 421113
461636 397528
468254 298152
329871 294594
374787 213141
349056 299400
157824 375747
127664 310858
51614 316107
247619 483715
99405 317027
451439 413890
271303 104915
14174 237451
72169 43889
267943 170586
111172 ...

output:

503694719

result:

ok answer is '503694719'

Test #17:

score: 4
Accepted
time: 50ms
memory: 53100kb

input:

99997
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
27...

output:

951546685

result:

ok answer is '951546685'

Test #18:

score: 4
Accepted
time: 59ms
memory: 54012kb

input:

100000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

398299966

result:

ok answer is '398299966'

Test #19:

score: 4
Accepted
time: 100ms
memory: 52276kb

input:

49994
16773 18084
13652 26028
29320 22500
8168 20391
20712 13289
18306 48732
1147 32403
22074 29376
42713 11128
26847 2494
20937 3907
44148 35349
27897 4800
7299 31995
33721 5113
31418 10206
19747 35922
10414 25963
18776 42084
44938 6516
4800 5329
41176 17864
31066 12752
29923 33698
47504 37268
4724...

output:

311193151

result:

ok answer is '311193151'

Test #20:

score: 4
Accepted
time: 144ms
memory: 96324kb

input:

79998
15767 34291
71245 14457
74445 58864
16367 6779
48359 64486
19508 48504
62217 20603
37223 443
59509 35966
38405 16920
79413 77556
27559 51976
66736 3647
41686 52728
46231 43331
34940 36057
61287 64199
76627 37116
21332 78604
27326 78434
58838 67326
24178 59289
10708 15944
14521 15352
23285 2543...

output:

108272378

result:

ok answer is '108272378'

Test #21:

score: 4
Accepted
time: 233ms
memory: 181152kb

input:

99999
14680 98099
68941 56143
16160 83923
32354 64072
19605 7048
24721 7369
32025 33248
57959 42630
48493 52559
48493 15160
76901 41756
31947 88634
98862 48493
70561 81999
81064 6357
29348 88172
36474 76470
70131 49915
12930 22381
25437 70561
70561 56236
70561 43957
17512 54072
48987 9540
42841 2154...

output:

38247969

result:

ok answer is '38247969'

Test #22:

score: 4
Accepted
time: 227ms
memory: 100268kb

input:

99996
81219 46611
27070 96230
88963 28320
47132 90466
47025 55027
56136 29854
12528 51209
51703 49946
85094 23069
28768 29508
51373 56376
21628 27271
75141 74333
86616 42671
47071 81610
71794 38614
95689 68213
21472 76729
95826 1
7067 56421
9255 1
46816 26963
68196 56713
83546 84190
92874 63215
4799...

output:

881239389

result:

ok answer is '881239389'

Test #23:

score: 4
Accepted
time: 1012ms
memory: 714036kb

input:

499999
328444 232129
34137 337939
1 2770
145619 337672
223675 257443
252889 184274
435369 80009
390302 338638
87899 38243
328444 374192
95368 379319
203463 293410
158770 373327
153849 111860
303903 481356
129222 216039
287062 175092
485781 979
359098 421597
5354 229733
227881 30640
142194 126688
344...

output:

213231046

result:

ok answer is '213231046'

Test #24:

score: 4
Accepted
time: 1193ms
memory: 724544kb

input:

499996
234812 237052
231031 104664
102145 299812
273901 51367
487834 495839
77385 276903
393563 119918
136245 318870
68288 88488
185218 237190
347758 398936
492387 460746
287846 454723
400936 222847
77067 485362
113343 113127
25637 124859
146819 460819
118564 204986
1597 420874
406709 470358
318130 ...

output:

775170

result:

ok answer is '775170'

Test #25:

score: 4
Accepted
time: 985ms
memory: 711832kb

input:

499999
413164 1
45178 10034
77624 1
1 295033
113198 162474
5742 45178
76083 379306
271416 134250
130336 491344
426378 1
10340 45178
14040 430225
1 468965
210040 482376
22963 473681
173835 464785
73841 103763
209733 383125
469692 1
1 14003
375214 363310
45178 208777
16359 260731
340784 490818
491344 ...

output:

247536705

result:

ok answer is '247536705'

Extra Test:

score: 0
Extra Test Passed