POJ 3321

发表于 |

题目

给一颗树，N个节点，每个节点初始权值为1。要完成M个操作。

有2种操作：

  1. 将指定节点权值和1抑或
  2. 询问指定子树的权值和

数据范围

$$ 0 \leq N, M \leq 10^5$$

做法

因为涉及到子树的操作，所以用Dfs序将树转化为序列。相应的，操作就成了序列上的单点修改区间求和。线段树或者树状数组维护即可。

代码

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <cstdio>
#include <vector>
using namespace std;
const int MAX_N = 1e5 + 5;
struct ST
{
  int dat[MAX_N << 2];
  void pushUp(int k)
  {
    dat[k] = dat[2 * k + 1] + dat[2 * k + 2];
  }
  void build(int l, int r, int k)
  {
    if (r - l == 1) {
      dat[k] = 1;
      return;
    }
    build(l, (l + r) / 2, 2 * k + 1);
    build((l + r) / 2, r, 2 * k + 2);
    pushUp(k);
  }
  void update(int pos, int l, int r, int k)
  {
    if (r - l == 1) {
      dat[k] ^= 1;
      return;
    }
    int mid = (l + r) / 2;
    if (pos < mid) update(pos, l, (l + r) / 2, 2 * k + 1);
    else update(pos, (l + r) / 2, r, 2 * k + 2);
    pushUp(k);
  }
  int query(int a, int b, int l, int r, int k)
  {
    if (b <= l || r <= a) return 0;
    if (a <= l && r <= b) return dat[k];
    int vl = query(a, b, l, (l + r) / 2, 2 * k + 1);
    int vr = query(a, b, (l + r) / 2, r, 2 * k + 2);
    return vl + vr;
  }
};
struct Graph
{
  struct Edge {int to, nxt;};
  int cnt;
  int head[MAX_N];
  Edge e[MAX_N << 1];
  void init(int n)
  {
    cnt = 0;
    for (int i = 0; i < n; ++i) head[i] = -1;
  }
  void addEdge(int u, int v)
  {
    e[cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt++;
    e[cnt].to = u; e[cnt].nxt = head[v]; head[v] = cnt++;
  }
};
int N, M;
int vs[MAX_N];
int st[MAX_N], ed[MAX_N];
ST segTree;
Graph G;
void getDfn(int v, int fa, int &id)
{
  vs[++id] = v;
  st[v] = id;
  for (int i = G.head[v]; i != -1; i = G.e[i].nxt) {
    int u = G.e[i].to;
    if (u != fa) {
      getDfn(u, v, id);
    }
  }
  ed[v] = id;
}
int main()
{
  scanf("%d", &N);
  G.init(N);
  for (int i = 1; i < N; ++i) {
    int a, b; scanf("%d%d", &a, &b);
    G.addEdge(--a, --b);
  }
  int id = -1;
  getDfn(0, -1, id);
  segTree.build(0, N, 0);
  scanf("%d", &M);
  while (M--) {
    char op[2]; int x;
    scanf("%s%d", op, &x);
    --x;
    if (op[0] == 'Q') {
      printf("%d\n", segTree.query(st[x], ed[x] + 1, 0, N, 0));
    } else {
      segTree.update(st[x], 0, N, 0);
    }
  }
  return 0;
}

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <cstdio>
#include <vector>
using namespace std;
const int MAX_N = 1e5 + 5;
struct BIT
{
  int n;
  int dat[MAX_N];
  void init(int n_)
  {
    n = n_;
    for (int i = 0; i <= n; ++i) dat[i] = 0;
    for (int i = 1; i <= n; ++i) update(i);
  }
  void update(int i)
  {
    int v = sum(i) - sum(i - 1) ? -1 : 1;
    while (i <= n) {
      dat[i] += v;
      i += i & -i;
    }
  }
  int sum(int i)
  {
    int s = 0;
    while (i > 0) {
      s += dat[i];
      i -= i & -i;
    }
    return s;
  }
};
struct Graph
{
  struct Edge {int to, nxt;};
  int cnt;
  int head[MAX_N];
  Edge e[MAX_N << 1];
  void init(int n)
  {
    cnt = 0;
    for (int i = 0; i < n; ++i) head[i] = -1;
  }
  void addEdge(int u, int v)
  {
    e[cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt++;
    e[cnt].to = u; e[cnt].nxt = head[v]; head[v] = cnt++;
  }
};
int N, M;
int vs[MAX_N];
int st[MAX_N], ed[MAX_N];
BIT bit;
Graph G;
void getDfn(int v, int fa, int &id)
{
  vs[++id] = v;
  st[v] = id;
  for (int i = G.head[v]; i != -1; i = G.e[i].nxt) {
    int u = G.e[i].to;
    if (u != fa) {
      getDfn(u, v, id);
    }
  }
  ed[v] = id;
}
int main()
{
  scanf("%d", &N);
  G.init(N);
  for (int i = 1; i < N; ++i) {
    int a, b; scanf("%d%d", &a, &b);
    G.addEdge(--a, --b);
  }
  int id = 0;
  // int id = -1;
  getDfn(0, -1, id);
  bit.init(N);
  scanf("%d", &M);
  while (M--) {
    char op[2]; int x;
    scanf("%s%d", op, &x);
    --x;
    if (op[0] == 'Q') {
      printf("%d\n", bit.sum(ed[x]) - bit.sum(st[x] - 1));
    } else {
      bit.update(st[x]);
    }
  }
  return 0;
}

注意

线段树的下标从0开始，而树状数组的下标从1开始。