QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#416174#5403. 树数术chroneZ20 2474ms299880kbC++173.9kb2024-05-21 16:46:322024-05-21 16:46:32

Judging History

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

  • [2024-05-21 16:46:32]
  • 评测
  • 测评结果:20
  • 用时:2474ms
  • 内存:299880kb
  • [2024-05-21 16:46:32]
  • 提交

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() {
  // freopen("tree.in", "r", stdin);
  // freopen("tree.out", "w", stdout);
  // 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]);
    }
    sort(S.begin(), S.end());
    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: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2474ms
memory: 299880kb

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:

414919
464289
494925
386270
442147
364276
401975
454211
431471
299450
366103
265439
325816
163975
348433
216139
401719
16634
200359
27351
103756
169847
290266
463858
339876
150935
151290
229206
198892
444771
398455
419146
293826
372006
432125
80459
385306
415228
62365
222331
474164
276309
284536
238...

result:

wrong answer 1st lines differ - expected: '121987', found: '414919'

Subtask #2:

score: 20
Accepted

Test #2:

score: 20
Accepted
time: 2152ms
memory: 261344kb

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: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 141ms
memory: 102092kb

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:

wrong answer 33324th lines differ - expected: '23208', found: '30931'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%