-
Notifications
You must be signed in to change notification settings - Fork 11
Expand file tree
/
Copy pathADAVISIT.cpp
More file actions
128 lines (128 loc) · 3.36 KB
/
Copy pathADAVISIT.cpp
File metadata and controls
128 lines (128 loc) · 3.36 KB
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// Ivan Carvalho
// Solution to https://www.spoj.com/problems/ADAVISIT/
#include <algorithm>
#include <cstdio>
#include <vector>
#define MP make_pair
#define LSOne(S) (S & (-S))
using namespace std;
typedef pair<int, int> ii;
const int MAXN = 4 * 1e5 + 10;
const ii NULO = MP(MAXN, MAXN);
int n, dfsNum, chainNum, chainPtr, nivel[MAXN], pai[MAXN], chainPos[MAXN],
chainId[MAXN], chainHead[MAXN], bit[MAXN], vetor[MAXN], tamanho[MAXN];
ii arvore[8 * MAXN], vetorzao[2 * MAXN];
vector<int> grafo[MAXN];
void update_bit(int pos, int val) {
while (pos < MAXN) {
bit[pos] += val;
pos += LSOne(pos);
}
}
int query_bit(int pos) {
int ans = 0;
while (pos > 0) {
ans += bit[pos];
pos -= LSOne(pos);
}
return ans;
}
void dfs(int x, int p) {
vetor[x] = ++dfsNum;
vetorzao[dfsNum] = MP(nivel[x], x);
tamanho[x]++;
for (int v : grafo[x]) {
if (v == p) continue;
nivel[v] = nivel[x] + 1;
pai[v] = x;
dfs(v, x);
tamanho[x] += tamanho[v];
vetorzao[++dfsNum] = MP(nivel[x], x);
}
}
void HLD(int x, int p) {
if (!chainHead[chainNum]) {
chainHead[chainNum] = x;
}
chainId[x] = chainNum;
chainPos[x] = ++chainPtr;
if (tamanho[x] == 1) return;
int sc = -1, maximo = 0;
for (int v : grafo[x]) {
if (v == p) continue;
if (tamanho[v] > maximo) {
maximo = tamanho[v];
sc = v;
}
}
HLD(sc, x);
for (int v : grafo[x]) {
if (v == p || v == sc) continue;
chainNum++;
HLD(v, x);
}
}
void build_seg(int pos, int left, int right) {
if (left == right) {
arvore[pos] = vetorzao[left];
return;
}
int mid = (left + right) / 2;
build_seg(2 * pos, left, mid);
build_seg(2 * pos + 1, mid + 1, right);
arvore[pos] = min(arvore[2 * pos], arvore[2 * pos + 1]);
}
ii query_seg(int pos, int left, int right, int i, int j) {
if (left > right || left > j || right < i) return NULO;
if (left >= i && right <= j) {
return arvore[pos];
}
int mid = (left + right) / 2;
return min(query_seg(2 * pos, left, mid, i, j),
query_seg(2 * pos + 1, mid + 1, right, i, j));
}
int LCA(int u, int v) {
return query_seg(1, 1, dfsNum, min(vetor[u], vetor[v]),
max(vetor[u], vetor[v]))
.second;
}
int query_up(int u, int v) {
int chainv, chainu;
chainv = chainId[v];
while (true) {
chainu = chainId[u];
if (chainv == chainu) {
update_bit(chainPos[v], 1);
update_bit(chainPos[u] + 1, -1);
break;
}
update_bit(chainPos[chainHead[chainu]], 1);
update_bit(chainPos[u] + 1, -1);
u = chainHead[chainu];
u = pai[u];
}
}
int doQuery(int u, int v) {
int ancestor = LCA(u, v);
query_up(u, ancestor);
query_up(v, ancestor);
update_bit(chainPos[ancestor], -1);
update_bit(chainPos[ancestor] + 1, 1);
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
grafo[u].push_back(v);
grafo[v].push_back(u);
}
pai[1] = -1;
dfs(1, -1);
build_seg(1, 1, dfsNum);
chainNum++;
HLD(1, -1);
for (int i = 1; i < n; i++) doQuery(i, i + 1);
for (int i = 1; i <= n; i++) printf("%d\n", query_bit(chainPos[i]));
return 0;
}