Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 动态树 Memory Limit Exceeded ？？ 包内存？？ 求高人解答

Posted by shuaige123 at 2012-06-04 14:03:36 on Problem 1330
```#include<cstdio>
#include<iostream>
using namespace std;
#define maxn 10100
struct edge_node{int next,y;}edge[maxn];
struct tree_node{int lc,rc,fa;
#define lc(x) tr[x].lc
#define rc(x) tr[x].rc
#define fa(x) tr[x].fa
}tr[maxn];
int first[maxn],ru[maxn],len,t,n,m;
inline void ins(int x,int y){
len++;
edge[len].y=y; edge[len].next=first[x]; first[x]=len;
return;
}
inline void dfs(int x,int last){
int k=first[x],y;
while (k!=-1){
y=edge[k].y;
if (y!=last){
fa(y)=x; lc(y)=rc(y)=0;
dfs(y,x);
}
k=edge[k].next;
}
return;
}
inline bool isroot(int x){return lc(fa(x))!=x && rc(fa(x))!=x;}
inline void l_rotate(int x){
int y,z; y=fa(x); z=fa(y);
if (lc(z)==y) lc(z)=x; if (rc(z)==y) rc(z)=x; fa(x)=z;
fa(lc(x))=y; rc(y)=lc(x); lc(x)=y; fa(y)=x;
return;
}
inline void r_rotate(int x){
int y,z; y=fa(x); z=fa(y);
if (lc(z)==y) lc(z)=x; if (rc(z)==y) rc(z)=x; fa(x)=z;
fa(rc(x))=y; lc(y)=rc(x); rc(x)=y; fa(y)=x;
return;
}
inline void splay(int x){
int y,z;
while (!isroot(x)){
y=fa(x); z=fa(y);
if (isroot(y)){
if (lc(y)==x) r_rotate(x);
else l_rotate(x);
}else{
if (lc(z)==y){
if (lc(y)==x) r_rotate(y),r_rotate(x);
else l_rotate(x),r_rotate(x);
}else{
if (lc(y)==x) r_rotate(x),l_rotate(x);
else l_rotate(y),l_rotate(x);
}
}
}
return;
}
inline void expose(int x){
int y=0;
while (x){
splay(x);
rc(x)=y; y=x; x=fa(x);
}
return;
}
inline int lca(int x,int y){
expose(y);
y=0;
while (x){
splay(x);
if (!fa(x)) return x;
rc(x)=y; y=x; x=fa(x);
}
}
int main(){
freopen("poj1330.in","r",stdin); freopen("poj1330.out","w",stdout);
int i,x,y;
scanf("%d",&t);
while (t--){
scanf("%d",&n);
memset(first+1,255,n*sizeof(int)); memset(ru+1,0,n*sizeof(int)); len=0;
for (i=1; i<n; i++){
scanf("%d%d",&x,&y); ru[y]++;
ins(x,y); ins(y,x);
}
for (i=1; i<=n; i++)
if (ru[i]==0){
fa(i)=lc(i)=rc(i)=0;
dfs(i,0);
break;
}
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
```

Followed by: