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

## 好裸的动态树，附上代码

Posted by chenwenxiao at 2012-02-16 15:04:45 on Problem 1330
```#include <cstdio>
#include <cstring>

const int maxn = 10001;

int f[maxn],s[maxn][2];
bool visit[maxn];
int n;

int updata(int x)
{

}

bool truefa(int x)
{
return f[x] && (s[f[x]][0] == x || s[f[x]][1] == x);
}

int rotate(int x,int p)
{
int y = f[x],z = f[y],son = s[x][p^1];
if (s[z][0] == y) s[z][0] = x;
if (s[z][1] == y) s[z][1] = x;
f[x] = z;
s[x][p^1] = y;
f[y] = x;
s[y][p] = son;
f[son] = y;
updata(y);
updata(x);
return 0;
}

int splay(int x)
{
while (truefa(x))
{
int y = f[x],z = f[y],p,q;
if (truefa(y))
{
if (x == s[y][0]) p = 0; else p = 1;
if (y == s[z][0]) q = 0; else q = 1;
if (p == q) {rotate(y,q); rotate(x,p);}
else {rotate(x,p); rotate(x,q);}
}
else if (s[y][0] == x) rotate(x,0); else rotate(x,1);
}
return 0;
}

int access(int p)
{
int q;
for (q = 0; p > 0; p = f[p])
{
splay(p);
s[p][1] = q;
updata(q = p);
}
return q;
}

int main()
{
freopen("1330.in","r",stdin);
freopen("1330.out","w",stdout);
{
memset(f,0,sizeof(f));
memset(s,0,sizeof(s));
scanf("%d",&n);
for (i = 1; i < n; ++i)
{
scanf("%d%d",&j,&k);
f[k] = j;
}
scanf("%d%d",&j,&k);
access(j);
printf("%d\n",access(k));
}
return 0;
}
```

Followed by: