QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#416188#5403. 树数术chroneZ100 ✓2238ms292932kbC++173.8kb2024-05-21 17:03:212024-05-21 17:03:22

Judging History

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

  • [2024-05-21 17:03:22]
  • 评测
  • 测评结果:100
  • 用时:2238ms
  • 内存:292932kb
  • [2024-05-21 17:03:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int N = 7e5 + 10;
int n; vector<int> G[N];

namespace Tree {
  int dep[N], siz[N], son[N], fa[N], top[N], dfn[N], dn;
  inline void dfs1(int u) {
    son[u] = -1, siz[u] = 1;
    for(auto v : G[u]) {
      if(v == fa[u]) continue;
      fa[v] = u, dep[v] = dep[u] + 1;
      dfs1(v);
      siz[u] += siz[v];
      if(son[u] == -1 || siz[son[u]] < siz[v]) son[u] = v;
    }
  }
  int seq[N << 1], m, fir[N];
  inline void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++dn;
    seq[++m] = u; fir[u] = m;
    if(son[u] == -1) return;
    dfs2(son[u], t);
    seq[++m] = u;
    for(auto v : G[u]) {
      if(v == fa[u] || v == son[u]) continue;
      dfs2(v, v);
      seq[++m] = u;
    }
  }
  inline bool subt(int u, int v) {
    return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + siz[u];
  }

  int st[21][N << 1];
  inline void buildst() {
    for(int i = 1; i <= m; i++) {
      st[0][i] = seq[i];
    }
    for(int i = 1; i <= 20; i++) {
      for(int j = 1; j + (1 << i) - 1 <= m; j++) {
        int l = st[i - 1][j], r = st[i - 1][j + (1 << i - 1)];
        st[i][j] = dep[l] < dep[r] ? l : r;
      }
    }
  }
  inline int lca(int u, int v) {
    int l = fir[u], r = fir[v];
    if(l > r) swap(l, r);
    int L = __lg(r - l + 1);
    int x = st[L][l], y = st[L][r - (1 << L) + 1];
    return dep[x] < dep[y] ? x : y;
  }

  void build() {
    dfs1(1), dfs2(1, 1);
    assert(m == 2 * n - 1);
    buildst();
  }
}
using Tree::subt, Tree::lca;
int m, Q, a[N];

struct Info {
  int A, res;
  int id, l, r;
};
vector<Info> res;
struct SegmentTree {
  Info t[N << 2];
  inline int calc(int k, int l, int r, int p) {
    if(l == r) return subt(t[k].A, p);
    if(subt(p, t[k].A) && p != t[k].A) return 0;
    int mid = l + r >> 1;
    // if(subt(p, t[k << 1].A) && p != t[k << 1].A) return calc(k << 1 | 1, mid + 1, r, p);
    // else return calc(k << 1, l, mid, p) + t[k].res - t[k << 1].res;
    if(subt(t[k << 1].A, p)) return calc(k << 1, l, mid, p) + t[k].res - t[k << 1].res;
    else return calc(k << 1 | 1, mid + 1, r, lca(t[k << 1].A, p));
  }
  inline void build(int k, int l, int r) {
    t[k].id = k, t[k].l = l, t[k].r = r;
    if(l == r) {
      t[k].A = a[l];
      t[k].res = 1;
      return;
    }
    int mid = l + r >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    t[k].A = lca(t[k << 1].A, t[k << 1 | 1].A);
    t[k].res = t[k << 1].res + calc(k << 1 | 1, mid + 1, r, t[k << 1].A);
  }
  inline void query(int k, int l, int r, int x, int y) {
    if(x <= l && r <= y) return res.push_back(t[k]), void();
    int mid = l + r >> 1;
    if(x <= mid) query(k << 1, l, mid, x, y);
    if(mid < y) query(k << 1 | 1, mid + 1, r, x, y);
  }
} tr;

int L[N], R[N];

inline void read(int &x) {
  char ch = getchar(); x = 0;
  while(!isdigit(ch)) ch = getchar();
  while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
}

int main() {
  // ios::sync_with_stdio(false);
  // cin.tie(nullptr), cout.tie(nullptr);
  
  read(n), read(m), read(Q);
  for(int i = 1; i < n; i++) {
    int u, v; read(u), read(v);
    G[u].push_back(v), G[v].push_back(u);
  }
  Tree::build();
  for(int i = 1; i <= m; i++) {
    read(a[i]);
  }
  tr.build(1, 1, m);
  while(Q--) {
    int k; read(k);
    res.clear();
    vector<pair<int, int>> S;
    for(int i = 1; i <= k; i++) {
      read(L[i]), read(R[i]);
      S.emplace_back(L[i], R[i]);
    }
    for(auto [l, r] : S) {
      tr.query(1, 1, m, l, r);
    }
    for(int i = 1; i < res.size(); i++) {
      res[i].A = lca(res[i - 1].A, res[i].A);
      res[i].res = res[i - 1].res + tr.calc(res[i].id, res[i].l, res[i].r, res[i - 1].A);
    }
    printf("%d\n", res.back().res);
  }
  // cerr << clock() * 1e3 / CLOCKS_PER_SEC << " ms\n";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1770ms
memory: 292932kb

input:

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

output:

121987
139520
87432
42773
311773
194269
177810
454211
417130
299450
366103
227736
186417
163975
292497
216139
401719
16634
192685
27351
52127
54938
142169
275076
339876
117003
51132
229206
187647
350043
398455
83905
100490
338070
356664
60211
366172
142627
16903
222331
471095
184145
170758
238393
14...

result:

ok 233333 lines

Subtask #2:

score: 20
Accepted

Test #2:

score: 20
Accepted
time: 2238ms
memory: 259224kb

input:

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

output:

211594
160846
176729
128251
32662
70710
74884
9095
68282
91324
154262
24279
31878
173468
75265
139715
91660
87525
194302
16875
81535
172911
29145
20483
151883
5255
9548
58890
38076
94152
14358
74859
48870
23981
41390
60976
13795
125823
427
26641
130620
174231
73241
55291
2364
78864
23391
4866
36002
...

result:

ok 699992 lines

Subtask #3:

score: 30
Accepted

Test #3:

score: 30
Accepted
time: 131ms
memory: 102040kb

input:

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

output:

9733
11330
8403
5136
22207
23231
12686
27288
23739
20937
18153
16379
8991
14036
11669
14685
20272
18955
21680
7927
21383
23576
14834
5714
15707
10013
7905
13254
13883
10446
16140
16796
11009
11912
15761
20419
11157
12192
14327
18260
19095
5239
4114
16522
7412
5005
16844
8747
19377
22600
12023
9161
9...

result:

ok 33333 lines

Subtask #4:

score: 40
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #4:

score: 40
Accepted
time: 2057ms
memory: 261576kb

input:

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

output:

129494
81962
52243
146978
53574
96058
72866
34286
184144
65111
77323
90610
168465
55995
66592
60741
118767
119126
150909
50321
114540
119576
122486
84546
19256
4585
22720
133448
124662
148500
173817
100034
135869
88299
68523
62880
73171
139874
90190
100601
100854
137709
106869
126901
40873
93249
136...

result:

ok 233333 lines