№ |
Отправитель |
Задача |
Язык |
Вердикт |
Время |
Память |
Отослано |
Протест. |
|
83887113 |
Дорешивание:
JKLover |
342E
- 19
|
C++17 (GCC 7-32)
|
Полное решение
|
1372 мс
|
28184 КБ
|
2020-06-16 06:28:15 |
2020-06-16 06:28:15 |
|
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
int out = 0, fh = 1;
char jp = getchar();
while ((jp > '9' || jp < '0') && jp != '-')
jp = getchar();
if (jp == '-')
fh = -1, jp = getchar();
while (jp >= '0' && jp <= '9')
out = out * 10 + jp - '0', jp = getchar();
return out * fh;
}
void print(int x)
{
if (x >= 10)
print(x / 10);
putchar('0' + x % 10);
}
void write(int x, char c)
{
if (x < 0)
putchar('-'), x = -x;
print(x);
putchar(c);
}
const int N = 2e5 + 10, K = 18;
int n, m, col[N], mind[N], dep[N], pos[N], st[N][K], Log[N], idx = 0, tmp[N], tot = 0;
vector<int> G[N];
void dfs(int x, int F)
{
++idx;
pos[x] = idx, st[idx][0] = dep[x];
for (int y : G[x])
if (y != F)
{
dep[y] = dep[x] + 1;
dfs(y, x);
++idx;
st[idx][0] = dep[x];
}
}
void init()
{
dfs(1, 0);
Log[1] = 0;
for (int i = 2; i <= idx; ++i)
Log[i] = Log[i >> 1] + 1;
for (int j = 1; j < K; ++j)
for (int i = 1; i + (1 << j) - 1 <= idx; ++i)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int dis(int x, int y)
{
int l = pos[x], r = pos[y];
if (l > r)
swap(l, r);
int d = dep[x] + dep[y], k = Log[r - l + 1];
return d - 2 * min(st[l][k], st[r - (1 << k) + 1][k]);
}
queue<int> q;
void ReBuild()
{
tot = 0;
for (int i = 1; i <= n; ++i)
if (col[i])
{
mind[i] = 0;
q.push(i);
}
else
mind[i] = n;
while (!q.empty())
{
int x = q.front();
q.pop();
for (int y : G[x])
if (mind[y] == n)
{
mind[y] = mind[x] + 1;
q.push(y);
}
}
}
int main()
{
n = read(), m = read();
for (int i = 1; i < n; ++i)
{
int u = read(), v = read();
G[u].push_back(v);
G[v].push_back(u);
}
init();
col[1] = 1;
ReBuild();
int t = sqrt(m);
for (int i = 1; i <= m; ++i)
{
int op = read(), x = read();
if (op == 1)
{
col[x] = 1;
tmp[++tot] = x;
}
else
{
int ans = mind[x];
for (int j = 1; j <= tot; ++j)
ans = min(ans, dis(tmp[j], x));
write(ans, '\n');
}
if (i % t == 0)
ReBuild();
}
return 0;
}
Время: ? ms, память: ? КБ