General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
83887113 Practice:
JKLover
342E - 19 GNU C++17 Accepted 1372 ms 28184 KB 2020-06-16 06:28:15 2020-06-16 06:28:15
 
 
→ Source
//%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;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details