这为什么会全TLE呢?
查看原帖
这为什么会全TLE呢?
183603
SUNCHAOYI废物生成器楼主2020/7/30 22:12

本地运行挺好的呀,下载了第一个数据,运行也立刻出结果(放在IDE上也一样)。求差错qwq:

#include <iostream>
#include <cstdio>
#define maxlog 20
using namespace std;
const int MAX = 500050;
int n,m,s,cnt,head[MAX],dep[MAX],f[MAX][25];
struct node
{
	int to,nxt;
} edge[MAX];
void _add (int x,int y);
int pre (int x,int father);
int LCA (int x,int y); 
int main ()
{
	scanf ("%d%d%d",&n,&m,&s);
	for (int i = 1;i < n;++i)
	{
		int x,y;scanf ("%d%d",&x,&y);
		_add (x,y);_add (y,x);
	}
	//for (int i = 1;i <= cnt;++i) cout<<edge[i].nxt<<" "<<edge[i].to<<" "<<head[i]<<endl;
	pre (s,0);
	//for (int i = 1;i <= n;++i) cout<<dep[i]<<endl;
	for (int i = 1;i <= m;++i)
	{
		int x,y;scanf ("%d%d",&x,&y);
		printf ("%d\n",LCA (x,y));
	}
	return 0;
}
void _add (int x,int y)
{
	edge[++cnt].to = y;
	edge[cnt].nxt = head[x];
	head[x] = cnt;
}
int pre (int x,int father)
{
	f[x][0] = father;//x 的父结点为 father 
	dep[x] = dep[father] + 1;
	//f[i][j]  表示 i 的第 2 ^ j 辈祖先
	//f[i][j] = f[f[i][j - 1][j - 1] 
	for (int i = 0;i < maxlog;++i) f[x][i + 1] = f[f[x][i]][i];
	for (int i = head[x];i;i = edge[i].nxt)
		if (edge[i].to != father) pre (edge[i].to,x);
}
int LCA (int x,int y)
{
	if (dep[x] < dep[y]) swap (x,y);//保持 x 的深度大于 y 的
	for (int i = maxlog;i >= 0;--i)
	{
		if (dep[f[x][i]] >= dep[y]) x = f[x][i];//变为同一层
		if (x == y) return x;//已经找到 
	}
	for (int i = maxlog;i >= 0;--i)
	{
		if (f[x][i] != f[y][i])//如果不是同一个祖先
			x = f[x][i],y = f[y][i]; 
	}
	return f[x][0];//LCA 子结点 
}
2020/7/30 22:12
加载中...