| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
各位大神帮忙看一下为什么 总是MLE啊 谢谢了#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10005;
int tme,n;
int cnt;
int root;
int in[N];
int fa[N][17],deep[N];
struct node
{
int net;
int to;
}e[2*N];
int head[N];
void add (int a,int b)
{
cnt++;
e[cnt].to=b;
e[cnt].net=head[a];
head[a]=cnt;
}
void dfs(int x,int pre,int step)
{
fa[x][0]=pre;deep[x]=step;
for(int i=head[x];i;i=e[i].net)
{
int t=e[i].to;
dfs(t,x,step+1);
}
}
int lca(int x,int y)
{
int re;
if(deep[x]<deep[y]) swap(x,y);
for(int i=16;i>=0;i--)
{
if(deep[fa[x][i]]>=deep[y])
x=fa[x][i];
}
if(x==y) return x;
for(int i=16;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[x][i];
}
else re=fa[x][i];
}
return re;
}
int main()
{
scanf("%d",&tme);
while(tme--)
{
memset(head,0,sizeof(head));
memset(fa,0,sizeof(fa));
memset(in,0,sizeof(in));
memset(deep,0,sizeof(deep));
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
in[y]++;
}
for(int i=1;i<=n;i++)
{
if(in[i]==0)
{
root=i;
break;
}
}
dfs(root,root,1);
for(int j=1;j<=16;j++)
{
for(int i=1;i<=n;i++)
{
fa[i][j]=fa[fa[i][j-1]][j-1];
}
}
int c,d;
scanf("%d%d",&c,&d);
int ans=lca(c,d);
printf("%d\n",ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator