#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int LG = 20;
vector <int> g[N];
int dad[N][LG];
map <int, int> id[N];
int lvl[N], in[N], out[N], timp, card[N], inters[N], aib[N], n;
int lsb(int x)
{
return x & (-x);
}
void upd(int x, int val)
{
for (x; x <= n; x += lsb(x))
aib[x] += val;
}
int qry(int x)
{
int ans = 0;
for (x; x; x -= lsb(x))
ans += aib[x];
return ans;
}
void lifting() ///used
{
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i <= n; i++)
dad[i][j] = dad[dad[i][j - 1]][j - 1];
}
int lca(int x, int y)
{
int lg = 19;
while (lvl[x] < lvl[y])
{
if (lvl[x] <= lvl[dad[y][lg]])
y = dad[y][lg];
lg--;
}
lg = 19;
while (lvl[x] > lvl[y])
{
if (lvl[y] <= lvl[dad[x][lg]])
x = dad[x][lg];
lg--;
}
lg = 19;
while (x != y && lg > -1)
{
if(dad[x][lg] != dad[y][lg])
{
x = dad[x][lg];
y = dad[y][lg];
}
lg--;
}
if (x != y)
return dad[x][0];
return x;
}
int nrm;
void dfs(int nod)
{
in[nod] = ++timp;
for (auto son : g[nod])
{
if (son == dad[nod][0])
continue;
dad[son][0] = nod;
///id[nod][son] = ++nrm;
lvl[son] = lvl[nod] + 1;
dfs(son);
}
out[nod] = timp;
}
int label(int u)
{
if (u == 0)
return -1;
return qry(in[u]);
}
bool queryJoined(int u, int v)
{
return (label(u) == label(v) && label(u) == label(lca(u, v)));
}
int queryCCRep(int u)
{
int lg = 19;
while (0 <= lg)
{
if (label(u) == label(dad[u][lg]))
u = dad[u][lg];
lg--;
}
return u;
}
void initEdges()
{
for (int i = 1; i <= n; i++)
{
upd(i, 1);
card[i] = 1;
}
}
void splitEdge(int u, int v) ///u == dad[v][0]
{
int root = queryCCRep(u);
inters[id[u][v]] = card[root];
card[v] = card[root];
upd(in[v], 1);
upd(out[v] + 1, -1);
}
void joinEdge(int u, int v) ///u == dad[v][0]
{
int root = queryCCRep(u);
card[root] = card[root] + card[v] - inters[id[u][v]];
upd(in[v], -1);
upd(out[v] + 1, 1);
}
int queryVertex(int u)
{
return card[queryCCRep(u)];
}
bool edgestate[N];
pair <int, int> edges[N];
int main()
{
int m, q;
cin >> n >> m >> q;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
id[a][b] = id[b][a] = i;
edges[i] = {a, b};
edgestate[i] = false;
}
lvl[1] = 1;
dfs(1);
lifting();
initEdges();
for (int i = 1; i <= m; i++)
{
int a, b, e;
cin >> e;
a = edges[e].first;
b = edges[e].second;
if (dad[a][0] == b)
swap(a, b);
if (edgestate[id[a][b]] == false)
{
edgestate[id[a][b]] = true;
joinEdge(a, b);
}
else
{
edgestate[id[a][b]] = false;
splitEdge(a, b);
}
}
for (int i = 1; i <= q; i++)
{
int a;
cin >> a;
cout << queryVertex(a) << '\n';
}
return 0;
}
Compilation message
synchronization.cpp: In function 'void upd(int, int)':
synchronization.cpp:16:10: warning: statement has no effect [-Wunused-value]
16 | for (x; x <= n; x += lsb(x))
| ^
synchronization.cpp: In function 'int qry(int)':
synchronization.cpp:22:10: warning: statement has no effect [-Wunused-value]
22 | for (x; x; x -= lsb(x))
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
5 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Incorrect |
4 ms |
7360 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
201 ms |
35916 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7364 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
4 ms |
7380 KB |
Output is correct |
6 |
Correct |
7 ms |
7632 KB |
Output is correct |
7 |
Correct |
48 ms |
10708 KB |
Output is correct |
8 |
Correct |
579 ms |
40192 KB |
Output is correct |
9 |
Correct |
579 ms |
40224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
543 ms |
40308 KB |
Output is correct |
2 |
Correct |
389 ms |
39500 KB |
Output is correct |
3 |
Correct |
389 ms |
39736 KB |
Output is correct |
4 |
Correct |
405 ms |
39680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |