Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

好裸的动态树,附上代码

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()
{
    int i,j,k,task;
    freopen("1330.in","r",stdin);
    freopen("1330.out","w",stdout);
    for (scanf("%d",&task); task > 0; --task)
    {
        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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator