题意

一棵\(n\)个点的树，点从\(1\)到\(n\)编号。每个点可能有两种颜色：黑或白。

我们定义\(dist(a,b)\)为点\(a\)至点\(b\)路径上的边个数。

一开始所有的点都是黑色的。

要求作以下操作：

\(0 i\) 将点\(i\)的颜色反转（黑变白，白变黑）

\(1 v\) 询问\(dist(u,v)\)的最小值，\(u\)与\(v\)可以相同，显然如果\(v\)是白点，查询得到的值一定是\(0\)

特别地，如果作\(1\)操作时树上没有白点，输出\(-1\)。

Sol

动态点分治+堆

每次从这个点不断向上层重心更新，每个点用堆维护到它最近的白点

查询，暴力向上跳重心，每次取出最近的点求\(lca\)，取\(dist\)的\(min\)

好像比\(QTREE4\)简单

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int _(1e5 + 5);

IL int Input(){

	RG int x = 0, z = 1; RG char c = getchar();

	for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

	for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

	return x * z;

}

int n, q, col[_], frt[_], first[_], cnt;

int st[20][_ << 1], lg[_ << 1], deep[_], id[_], len;

int size[_], mx[_], vis[_], rt, num, tot;

struct Edge{

	int to, next;

} edge[_ << 1];

struct Data{

	int u, dis;

	IL int operator <(RG Data B) const{

		return dis > B.dis;

	}

};

priority_queue <Data> Q[_];

IL void Add(RG int u, RG int v){

	edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++;

}

IL void GetRoot(RG int u, RG int ff){

	size[u] = 1, mx[u] = 0;

	for(RG int e = first[u]; e != -1; e = edge[e].next){

		RG int v = edge[e].to;

		if(vis[v] || v == ff) continue;

		GetRoot(v, u);

		size[u] += size[v];

		mx[u] = max(mx[u], size[v]);

	}

	mx[u] = max(mx[u], num - mx[u]);

	if(mx[u] < mx[rt]) rt = u;

}

IL void Solve(RG int u){

	vis[u] = 1;

	for(RG int e = first[u]; e != -1; e = edge[e].next){

		RG int v = edge[e].to;

		if(vis[v]) continue;

		num = size[v], rt = 0;

		GetRoot(v, u);

		frt[rt] = u, Solve(rt);

	}

}

IL void Dfs(RG int u, RG int ff){

	st[0][++len] = deep[u], id[u] = len;

	for(RG int e = first[u]; e != -1; e = edge[e].next){

		RG int v = edge[e].to;

		if(v == ff) continue;

		deep[v] = deep[u] + 1;

		Dfs(v, u);

		st[0][++len] = deep[u];

	}

}

IL int Dis(RG int u, RG int v){

	RG int dis = deep[u] + deep[v];

	u = id[u], v = id[v];

	if(u > v) swap(u, v);

	RG int lgn = lg[v - u + 1];

	return dis - 2 * min(st[lgn][u], st[lgn][v - (1 << lgn) + 1]);

}

IL int Query(RG int x){

	RG int ans = 2e9;

	for(RG int u = x; u; u = frt[u]){

		while(!Q[u].empty() && !col[Q[u].top().u]) Q[u].pop();

		if(!Q[u].empty()) ans = min(ans, Dis(x, Q[u].top().u));

	}

	return ans;

}

IL void Update(RG int x){

	for(RG int u = x; u; u = frt[u]){

		while(!Q[u].empty() && !col[Q[u].top().u]) Q[u].pop();

		Q[u].push((Data){x, Dis(u, x)});

	}

}

IL void Modify(RG int x){

	if(col[x]) --tot, col[x] ^= 1;

	else ++tot, col[x] ^= 1, Update(x);

}

int main(RG int argc, RG char *argv[]){

	n = Input(), Fill(first, -1), mx[0] = n + 1;

	for(RG int i = 1; i < n; ++i){

		RG int u = Input(), v = Input();

		Add(u, v), Add(v, u);

	}

	Dfs(1, 0);

	for(RG int i = 2; i <= len; ++i) lg[i] = lg[i >> 1] + 1;

	for(RG int j = 1; j <= lg[len]; ++j)

		for(RG int i = 1; i + (1 << j) - 1 <= len; ++i)

			st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);

	num = n, GetRoot(1, 0), Solve(rt);

	q = Input();

	for(RG int i = 1, x; i <= q; ++i){

		if(Input()) x = Input(), tot ? printf("%d\n", Query(x)) : puts("-1");

		else x = Input(), Modify(x);

	}

	return 0;

}

巴特西

SPOJ QTREE5

题意

Sol

最新文章

热门文章