顯示具有 tree 標籤的文章。 顯示所有文章
顯示具有 tree 標籤的文章。 顯示所有文章

2012年10月10日 星期三

uva 11615 - Family Tree

Problem

tree 
#include<stdio.h>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
using namespace std;

int A,B,N;
vector<int>lvl;
void init(){
    int a=0,c=1;
    rep(i,20)a+=c,c*=2,lvl.push_back(a);
}
int getL(int a){
    rep(i,20)if(a<=lvl[i])return i;
}
void ans(){
    int a=getL(A)+1,b=getL(B)+1,c=lvl[N-1];
    if(DBG)printf("a,b,c: %d %d %d\n",a,b,c);
    if(a>b)c-=(lvl[N-a]-1);
    else c-=(lvl[N-b]-1);
    printf("%d\n",c);
}
int main(){
    int n;
    init();
    scanf("%d",&n);
    rep(i,n)scanf("%d%d%d",&N,&A,&B),ans();
}
張貼者： 於 沒有留言:
標籤： ,

uva 10938 - Flea circus

problem

LCA - Tarjan離線解


#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int N,M,id[5010],dis[5010],p[5010],qry[500][2],lca[5010][5010];
vector<int>egs[5000],qeg[5000];
int find(int a){
    if(id[a]==a)return a;
    return id[a]=find(id[a]);
}
void merge(int c,int p){
    if(DBG)printf("merge %d to %d\n",c,p);
    id[find(c)]=find(p);
    if(DBG)printf("id[%d]=%d\n",c,id[find(c)]);
}
void tarjan(int c){
    if(DBG)printf("tarjan: %d\n",c);
    id[c]=c;
    rep(i,egs[c].size()){
        if(id[egs[c][i]]<0){
            dis[egs[c][i]]=dis[c]+1,p[egs[c][i]]=c;
            tarjan(egs[c][i]);
            merge(egs[c][i],c);}
    }
    rep(i,qeg[c].size()){
        if(id[qeg[c][i]]>=0)lca[qeg[c][i]][c]=lca[c][qeg[c][i]]=find(qeg[c][i]);
    }
}
void raise(int a,int d,int d2,int &x,int &y){
    rep(i,d/2+d2)a=p[a];
    x=a;
    if(d%2){y=p[a];if(x>y)swap(x,y);}
}
void getP(int i,int &x,int &y){
    int a=qry[i][0],b=qry[i][1],
    c=lca[a][b],
    d1=dis[a]-dis[c],d2=dis[b]-dis[c];
    if(DBG)printf("a b c d1 d2 %d %d %d %d %d\n",a,b,c,d1,d2);
    if(c==a)raise(b,(d2),0,x,y);
    else if(c==b)raise(a,(d1),0,x,y);
    else if(d1>d2)raise(a,d1-d2,d2,x,y);
    else if(d1<d2)raise(b,d2-d1,d1,x,y);
    else x=c;
}
void ans(){
    memset(dis,-1,sizeof(dis));
    memset(id,-1,sizeof(id));
    dis[1]=0;
    tarjan(1);
    if(DBG)rep(i,M)printf("lca %d %d: %d\n",qry[i][0],qry[i][1],lca[qry[i][0]][qry[i][1]]);
    int x,y;
    rep(i,M){
        x=-1,y=-1;
        getP(i,x,y);
        if(x>0&&y>0)printf("The fleas jump forever between %d and %d.\n",x,y);
        else printf("The fleas meet at %d.\n",x);
    }
}
int main(){
    int a,b,c,n,m;
    while(scanf("%d",&N)==1){
        if(!N)break;
        memset(dis,0,sizeof(dis));rep(i,500)qeg[i].clear();
        rep(i,5000)egs[i].clear();
        rep(i,N-1)scanf("%d%d",&a,&b),egs[a].push_back(b),egs[b].push_back(a);
        scanf("%d",&M);
        rep(i,M){
            scanf("%d%d",&qry[i][0],&qry[i][1]);
            qeg[qry[i][0]].push_back(qry[i][1]),
            qeg[qry[i][1]].push_back(qry[i][0]);
        }
        ans();
    }
}
張貼者： 於 沒有留言:
標籤： ,

2012年7月25日 星期三

uva 615- Is It A Tree?



  Is It A Tree? 

A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties.

  • There is exactly one node, called the root, to which no directed edges point.
  • Every node except the root has exactly one edge pointing to it.
  • There is a unique sequence of directed edges from the root to each node.
For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.
$\textstyle \parbox{.3\textwidth}{ \begin{center} \mbox{} \epsfxsize 1.5in \epsfbox{p615a.eps} \end{center}}$ $\textstyle \parbox{.4\textwidth}{ \begin{center} \mbox{} \epsfxsize 2in \epsfbox{p615b.eps} \end{center}}$ $\textstyle \parbox{.29\textwidth}{ \begin{center} \mbox{} \epsfxsize 1.5in \epsfbox{p615c.eps} \end{center}}$
In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.

Input 

The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero.

Output 

For each test case display the line ``Case k is a tree." or the line ``Case k is not a tree.", where kcorresponds to the test case number (they are sequentially numbered starting with 1).

Sample Input 


6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0
-1 -1

Sample Output 

Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.


Miguel A. Revilla
1999-03-24

notice: loop
張貼者： 於 沒有留言:
標籤： ,

2012年7月24日 星期二

uva 536 - Tree Recovery



  Tree Recovery 

Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes.
This is an example of one of her creations:

                                    D
                                   / \
                                  /   \
                                 B     E
                                / \     \
                               /   \     \ 
                              A     C     G
                                         /
                                        /
                                       F
To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree).
For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG.
She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).


Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree.
However, doing the reconstruction by hand, soon turned out to be tedious.
So now she asks you to write a program that does the job for her!

Input Specification 

The input file will contain one or more test cases. Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)Input is terminated by end of file.

Output Specification 

For each test case, recover Valentine's binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).

Sample Input 

DBACEGF ABCDEFG
BCAD CBAD

Sample Output 

ACBFGED
CDAB


tree reconstruction













張貼者：





於




沒有留言:
              

















標籤：
,
















          

        

          

        

2012年6月29日 星期五


          

        







線段樹(Segment Tree)










source: http://www.cnblogs.com/tanky_woo/archive/2010/09/25/1834523.html



線段樹(Segment Tree)





实际上还是称为区间树更好理解一些。
树：是一棵树，而且是一棵二叉树。
线段：树上的每个节点对应于一个线段(还是叫“区间”更容易理解，区间的起点和终点通常为整数)
同一层的节点所代表的区间，相互不会重叠。
叶子节点的区间是单位长度，不能再分了。











线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。a,b通常是整数。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2,b](除法去尾取整）。



线段树的基本用途：
线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分，按区间动态进行修改，而且还需要按区间多次进行查询，那么使用线段树可以达到较快查询速度。



线段树的构建



   createSeg   //以节点v为根建树、v对应区间为[l,r]
{
    对节点v初始化
     if (l!=r)
    {
        以v的左孩子为根建树、区间为[l,(l+r)/2]
        以v的右孩子为根建树、区间为[(l+r)/2+1,r]
    }
}



(浏览器似乎不太好用了，上面的代码点“插入代码”不管用，就直接贴出来了)







个人感觉线段树比较灵活，要多做一些题目才能对线段树有一个大概的掌握。
网上看见了一些线段树的资料，这里也贴出来。




线段树(区间树)Segment Tree

















張貼者：





於




沒有留言:
              

















標籤：
,






















Splay Tree















Demo: http://www.link.cs.cmu.edu/cgi-bin/splay/splay-cgi.pl

source:  http://www.fcicq.net/wp/?p=107




Splay Tree – 伸展树







假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计 一个简单方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。




重构方法



1、单旋：在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边。（除非x就是树根）
2、搬移至树根：在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边，然后重复这个操作直至x成为树根。
splay tree的重构方法和搬移至树根的方法相似，它也会沿着查找路径做自底向上的旋转，将被查找条目移至树根。但不同的是，它的旋转是成对进行的，顺序取决于查找路径的结构。为了在节点x处对树进行splay操作，我们需要重复下面的步骤，直至x成为树根为止：
1、第一种情况：如果x的父节点p(x)是树根，则旋转连接x和p(x)的边。（这种情况是最后一步）
2、第二种情况：如果p(x)不是树根，而且x和p(x)本身都是左孩子或者都是右孩子，则先旋转连接p(x)和x的祖父节点g(x)的边，然后再旋转连接x和p(x)的边。
3、第三种情况：如果p(x)不是树根，而且x是左孩子，p(x)是右孩子，或者相反，则先旋转连接x和p(x)的边，再旋转连接x和新的p(x)的边。
在节点x处进行splay操作的时间是和查找x所需的时间成比例的。splay操作不单是把x搬移到了树根，而且还把查找路径上的每个节点的深度都大致减掉了一半。




splay tree支持的操作



1、access(i,t):如果i在树t中，则返回指向它的指针，否则返回空指针。为了实现access(i,t)，可以从树t的根部向下查找 i。如果查找操作遇到了一个含有i的节点x，就在x处进行splay操作，并返回指向x的指针，访问结束。如果遇到了空指针，表示i不在树中，此时就在最 后一个非空节点处进行splay操作，然后返回空指针。如果树是空的，将忽略掉splay操作。
2、insert(i,t):将条目i插入树t中（假设其尚不存在）。为了实现insert(i,t)，首先执行split(i,t)，然后把t换成一个由新的包含有i的根节点组成的树，这个根节点的左右子树分别是split返回的树t1和t2。
3、delete(i,t):从树t中删除条目i（假设其已经存在）。为了实现delete(i,t)，首先执行access(i,t)，然后把t换成其左子树和右子树join之后的新树。
4、join(t1,t2):将树t1和t2合并成一棵树，其中包含之前两棵树的所有条目，并返回合并之后的树。这个操作假设t1中的所有条目都小于t2 中的条目，操作完成之后会销毁t1和t2。为了实现join(t1,t2)，首先访问t1中最大的条目i。访问结束之后，t1的根节点中包含的就是i，它 的右孩子显然为空。于是把t2作为这个根节点的右子树并返回完成之后的新树即可实现join操作。
5、split(i,t):构建并返回两棵树t1和t2，其中t1包含t中所有小于等于i的条目，t2包含t中所有大于i的条目。操作完成之后销毁t。为 了实现split(i,t)，首先执行access(i,t)，然后根据新根节点中的值是大于还是小于等于i来切断这个根节点的左链接或右链接，并返回形 成的两棵树。




Splay Tree的优势所在



由于Splay Tree仅仅是不断调整，并没有引入额外的标记，因而树结构与标准BST没有任何不同，从空间角度来看，它比Treap、Red-Black Tree、AVL要高效得多。因为结构不变，因此只要是通过左旋和右旋进行的操作对Splay Tree性质都没有丝毫影响，因而它也提供了BST中最丰富的功能，包括快速的拆分和合并（这里指的是将原树拆分成两棵子树，其中一棵子树所有节点都比另 一子树小，以及它的逆过程），并且实现极为便捷。这一点是其它结构较难实现的。其时间效率也相当稳定，和Treap基本相当。









張貼者：





於




沒有留言:
              

















標籤：
,
















        

      









訂閱：
文章 (Atom)