后几个测试点经测试似乎是读入上TLE了。
我的测试方法:在读入语句后面放上多余输出,原来AC的WA了,原来TLE的还是TLE,说明读入TLE了。
大佬们看一下是怎么回事,O(n)读入居然TLE:
#include <bits/stdc++.h>//希望有生之年能看到CCF用IOI赛制&CSP2022 rp++
//lca调了半天不行,算了用并查集
using namespace std;
const int maxn= 1e5+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;
}