rt,我在洛谷外的某一OJ提交时,取得了以下成绩:
CE 1(这个是手残)
RE 17(这个是我要说的)
但在洛谷上提交就AC了(虽然常数有点大)
在本地运行洛谷数据也会RE
调试发现RE在一个很神奇的地方(见代码注释)
还有手调了一个大数据,发现好像会无限递归然后爆栈(?
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,m,s,f[N][30],dep[N];
vector<int>v[N];
inline int read()
{
char ch=getchar();int s=0,w=1;
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9'){s=s*10+ch-48;ch=getchar();}
return s*w;
}
inline void dfs(int step,int faa)
{
dep[step]=dep[faa]+1;
f[step][0]=faa;
for(int i=1;(1<<i)<=dep[step];i++)
{
f[step][i]=f[f[step][i-1]][i-1];
}
for(int t:v[step])//RE在这里
{
if(t!=faa)
dfs(t,step);
}
}
inline int LCA(int u,int v)
{
if(dep[u]<dep[v])swap(u,v);
for(int i=20;i>=0;i--)
{
if(dep[f[u][i]]>=dep[v])u=f[u][i];
}
if(u==v)return v;
for(int i=20;i>=0;i--)
{
if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
}
return f[u][0];
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n=read(),m=read(),s=read();
for(int i=1;i<=n-1;i++)
{
int a=read(),b=read();
v[a].push_back(b);
v[b].push_back(a);
}
dfs(s,0);
for(int i=1;i<=m;i++)
{
int a=read(),b=read();
cout<<LCA(a,b)<<endl;
}
return 0;
}
救救孩子吧,孩子调这一题调两天了
但是链式前向星不会RE,但是我习惯写vector,而且其他题用vector也没RE