Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## dfs + 树状数组

Posted by zhouzp15 at 2017-01-20 17:15:21 on Problem 3321
```#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e5 + 5;
struct Node
{
int vertex;
Node *next;
} mem[N], *nbr[N];

int tree[N], l[N], r[N], n, clock;
bool pd[N];

#define lowbit(x) (x & -x)
void add(int idx, int delta) { while (idx <= n) tree[idx] += delta, idx += lowbit(idx); }
int sum(int idx) { int s = 0; while (idx > 0) s += tree[idx], idx -= lowbit(idx); return s; }

void dfs(int v, int &clock)
{
l[v] = ++clock;
for (Node *p = nbr[v]; p; p = p->next)
dfs(p->vertex, clock);
r[v] = clock;
}

int alloc = 0;
Node *newNode(int vertex, Node *next)
{
mem[alloc] = (Node){ vertex, next };
return &(mem[alloc++]);
}

int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int from, to;
scanf("%d%d", &from, &to);
nbr[from] = newNode(to, nbr[from]);
}
dfs(1, clock);
for (int i = 1; i <= n; i++) add(i, 1), pd[i] = true;

int m;
scanf("%d\n", &m);
for (int i = 1; i <= m; i++)
{
char op; int v;
scanf("%c %d\n", &op, &v);
if (op == 'C')
{

int idx = l[v];
if (pd[idx]) add(idx, -1), pd[idx] = false;
else add(idx, 1), pd[idx] = true;
} else
printf("%d\n", sum(r[v]) - sum(l[v] - 1));
}
return 0;
}```

Followed by: