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

## vector果然超时，贴一个AC代码

Posted by zxj1015 at 2015-04-20 20:22:51 on Problem 3321
```#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#include <deque>
#include <string.h>

using namespace std;

struct Node {
int index;
Node* next;
Node() {
next = NULL;
}
};

Node* tree[100100] = {0};
int bit[100100] = { 0 };
bool has[100100] = { 0 };
int low[100100] = { 0 };
int high[100100] = { 0 };

int Dfs(int start, int index) {
low[start] = index;
Node* pointer = tree[start];
while (pointer != NULL) {
int dst = pointer->index;
pointer = pointer->next;
high[dst] = Dfs(dst, index + 1);
index = high[dst];
}
return index;
}

void Change(int index, int value, const int N) {
while (index <= N) {
bit[index] += value;
index += index & -index;
}
}

int Query(int index) {
int sum_value = 0;
while (index > 0) {
sum_value += bit[index];
index -= index & -index;
}
return sum_value;
}

int main() {
freopen("/Users/zxj/Desktop/poj_input.txt", "r", stdin);
int N;
scanf("%d", &N);
for (int i = 0; i < N - 1; ++i) {
int father, son;
scanf("%d %d", &father, &son);
if (tree[father] == NULL) {
tree[father] = new Node();
tree[father]->index = son;
} else {
Node* p = new Node();
p->index = son;
p->next = tree[father];
tree[father] = p;
}
}

high[1] = Dfs(1, 1);
for (int i = 1; i <= N; ++i) {
Change(low[i], 1, N);
has[i] = 1;
}
int M;
scanf("%d", &M);
for (int i = 0; i < M; ++i) {
char buf[2];
int index;
scanf("%s %d", buf, &index);
if (buf[0] == 'Q') {
printf("%d\n", Query(high[index]) - Query(low[index] - 1));
} else {
int value = has[index] ? -1 : 1;
has[index] = !has[index];
Change(low[index], value, N);
}
}
}```

Followed by: