本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-12-04 12:01:42

作用：

能让并查集原地起飞

具体描述：

P5836这道题用并查集来做，TLE了，只得了 $\color{orange}\text{40分}$，提交记录。代码：

#include <bits\/stdc++.h>\/\/希望有生之年能看到CCF用IOI赛制&CSP2022 rp++
\/\/lca调了半天不行，算了用并查集
using namespace std;
const int maxn=	1e6+5;
int n,m;
char lx[maxn];
int f[maxn];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int find(int x)
{
	return x==f[x]?x:find(f[x]);
}

int main()
{
	for(int i=1;i<maxn;i++)f[i]=i;
	scanf("%d%d",&n,&m);
	scanf("%s",lx+1);
    int x,y;
    for(int i=1;i<n;i++)
    {
    	x=read();
    	y=read();
    	if(lx[x]==lx[y])
    	{
    		int ta=find(x);
			int tb=find(y);
			f[ta]=tb;\/\/将相同颜色弄成连通块
		}
    }
    int ai,bi;
    char ci;
    for(int i=1;i<=m;i++)
    {
    	ai=read();
    	bi=read();
    	scanf("%c",&ci);
    	if(find(ai)==find(bi)&&lx[ai]!=ci)printf("0");\/\/如果在同一个连通块且其中一个不符合要求，其他一定不符合要求
    	else printf("1");
    }
    
    return 0;
}

这份代码之所以TLE，是因为并查集find函数太慢，只需要将find函数修改为一下：

int find(int x)
{
	if(x==f[x])return x;
	return f[x]=find(f[x]);
}

就能让并查集原地起飞，快了30倍+，然后AC,吸氧后甚至拿了最优解排行首页（不吸氧在第二页），提交记录，代码：

#include <bits\/stdc++.h>\/\/希望有生之年能看到CCF用IOI赛制&CSP2022 rp++
\/\/lca调了半天不行，算了用并查集
using namespace std;
const int maxn=	1e6+5;
int n,m;
char lx[maxn];
int f[maxn];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int find(int x)
{
	if(x==f[x])return x;
	return f[x]=find(f[x]);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)f[i]=i;
	scanf("%s",lx+1);
    int x,y;
    for(int i=1;i<n;i++)
    {
    	x=read();
    	y=read();
    	if(lx[x]==lx[y])
    	{
    		int ta=find(x);
			int tb=find(y);
			f[ta]=tb;\/\/将相同颜色弄成连通块
		}
    }
    int ai,bi;
    char ci;
    for(int i=1;i<=m;i++)
    {
    	ai=read();
    	bi=read();
    	scanf("%c",&ci);
    	if(find(ai)==find(bi)&&lx[ai]!=ci)putchar('0');\/\/如果在同一个连通块且其中一个不符合要求，其他一定不符合要求
    	else putchar('1');
    }
    return 0;
}