问题标题: 酷町堂：LCA或MST求解6412

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,fa[100000];
bool map[100000];
struct node{
	int to,en,w;
	bool operator>(const node& tmp)const{
		return w>tmp.w;
	}	
};
priority_queue<node, vector<node>, greater<node> > p,q,tmp;

void init()
{
	for(int i=1;i<=n;i++)
		if(map[i])
			fa[i]=i;
}
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void unite(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y)
		return ;
	fa[x]=y;
}
bool same(int x,int y)
{
	if(find(x)==find(y))
		return true;
	return false;
}
int kruscal()
{
	int MST=0;
	init();
	while(!q.empty())
	{
		node u=q.top();
		tmp.push(u);
		q.pop();
		if(!same(u.en,u.to))	
		{
			unite(u.en,u.to);
			MST+=u.w;
		}
	}
	while(!tmp.empty())
	{
		q.push(tmp.top());
		tmp.pop();
	}
	return MST;
} 

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		p.push((node){x,y,z});
	}
	scanf("%d",&m);
	while(m--)
	{
		char opt;
		int x;
		cin>>opt;
		if(opt=='+')
		{
			cin>>x;
			map[x]=true;
			while(!p.empty())
			{
				node h=p.top();
				tmp.push(h);
				p.pop();
				if(h.en==x||h.to==x)
					q.push(h);
			}
			while(!tmp.empty())
			{
				p.push(tmp.top());
				tmp.pop();
			}
		}
		if(opt=='-')
		{
			scanf("%d",&x);
			map[x]=false;
			while(!q.empty())
			{
				node h=q.top();
				if(h.en!=x&&h.to!=x)
					tmp.push(h);
				q.pop();
			}
			while(!tmp.empty())
			{
				q.push(tmp.top());
				tmp.pop();
			}
		}
		if(opt=='?')
			printf("%d\n",kruscal());
	}
	return 0;
}

我先写了个Kruskal求动态MST思路，先发现读入字符问题，cin处理之后对拍样例，发现第一个输出的是6，而样例的是5，也显然是5.

后来发现Kruskal不能处理虚点（即不需要连接的点，但与要连接的点有关联），或者说要处理的MST不是真的MST

哪位Dalao帮我用Prim改写下这道题的Kruskal啊，或者帮我改下init的函数，因为我发现一定是init出了问题，但这涉及到Kruskal的本质，目前想不出来惹。

我的思路是如果是“+"就把接下来输入的这个点有直连的边加入要求的MST图中，如果是"-"就把输入的这个点有关的直连边删去，但好像有点问题。如果是"？"就求加入q队列的要求的MST图中。

当然我知道这道题正解是LCA，MST不加STL_map一定会TLE。如果能给出LCA思路更好。

赵逸凡在2021-05-16 19:01:40追加了内容