GYM102538G Giant Penguin

GYM102538G

Giant Penguin

给定一个无向图，每个点一开始都是黑色的，且满足每个点在不超过 \(k\) 个简单环里。要维护两种操作：

• 选择一个黑色的点，染成红色。
• 选择一个点，求所有红色点到这个点的距离的最小值。

\(0\le k\le 10,1\le n\le 10^5\)

---

假如这个题被出到了模拟里，显然有一档部分分是 \(k=0\)，即原图是一棵树。

很遗憾的是，其实感觉这个弱化问题没有太大的启发性，因为做法实在是太多了。😁

其中有一种做法用到一个叫点分树的东西。

---

点分树其实并不是一棵生成树，它的本质是将所有点重新排列，组合成一棵树形结构使得这棵树的深度不超过 \(\mathcal O(\log n)\)。

点分树还有另外一个性质：对于点分树上的两个点 \((u,v)\)，如果其 lca 为 \(x\)，则有 \(dis(u,v)=dis(u,x)+dis(v,x)\)。

具体构造其实是容易的：每次取出当前点集的重心，把重心的所有子树再建点分树，然后把这些点分树的根设为儿子。

假如原树是一条长度为 \(7\) 的链，点分树显然如下所示：

然后可以设 \(f(i)\) 表示 \(i\) 的子树内红点到 \(i\) 的最短距离，可以通过维护这个值来进行修改和查询。

对于一个点分树的子树，由于每个点最多在 \(k\) 个简单环中，所以跨越子树的边最多有 \(k\) 条（因为每条边都会带来一个简单环）那么只需要预处理根节点和这些边所连接的点到其他点的最短路即可。（因为如果想要从一个子树走到另一个子树，必然需要经过这种点。）

时间复杂度：\(\Theta(nk\log n)\)

参考代码：

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
#define elif else if
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
void fileio(const string &s)
{
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
const int INF=4e18;
inline int read()
{
	int x=0;
	bool flag=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			flag=0;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return (flag?x:~(x-1));
}
int n,m,k,cnt,S,q,dep[100010],vis[100010],usd[100010],sz[100010],mx[100010],p[100010],dis[100][100010],f[100010];
std::vector<int> G[100010];
void dfs(int x)
{
	sz[x]=1;
	usd[x]=cnt;
	for(int i:G[x])
		if(!vis[i]&&usd[i]!=cnt)
		{
			dfs(i);
			sz[x]+=sz[i];
		}
}
void dfs1(int x,int &rt)
{
	mx[x]=S-sz[x];
	usd[x]=cnt;
	for(int i:G[x])
		if(!vis[i]&&usd[i]!=cnt)
		{
			mx[x]=max(mx[x],sz[i]);
			dfs1(i,rt);
		}
	if(mx[x]<mx[rt])
		rt=x;
}
void bfs(int k,int x)
{
	queue<int> q;
	q.push(x);
	dis[k][x]=0;
	while(!q.empty())
	{
		int f=q.front();
		q.pop();
		for(int i:G[f])
			if(!vis[i]&&!dis[k][i])
			{
				dis[k][i]=dis[k][f]+1;
				q.push(i);
			}
	}
}
void build(int x,int fa)
{
	cnt++;
	dfs(x);
	S=sz[x];
	int rt=0;
	cnt++;
	dfs1(x,rt);
	vis[rt]=1;
	p[rt]=fa;
	dep[rt]=dep[fa]+1;
	bfs(dep[rt],rt);
	for(int i:G[rt])
		if(!vis[i])
			build(i,rt);
}
signed main()
{
	n=read();
	m=read();
	k=read();
	mx[0]=INF;
	while(m--)
	{
		int x=read(),y=read();
		G[x].push_back(y);
		G[y].push_back(x);
	}
	build(1,0);
	fill(f+1,f+1+n,INF);
	q=read();
	while(q--)
	{
		int opt=read();
		if(opt&1)
		{
			int x=read();
			for(int i=x;i;i=p[i])
				f[i]=min(f[i],dis[dep[i]][x]);
		}
		else
		{
			int x=read(),ans=INF;
			for(int i=x;i;i=p[i])
				ans=min(ans,dis[dep[i]][x]+f[i]);
			cout<<ans<<'\n';
		}
	}
	return 0;
}