• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-72  評論-126  文章-0  trackbacks-0
            http://acm.hdu.edu.cn/showproblem.php?pid=1512


            #include<stdio.h>
            #define MAX 100001

            struct Left_Heap{
                
            int left,right;
                
            int father;
                
            int pow;
                
            int deep;
            }hh[MAX];

            int find(int a)
            {
                
            while(a!=hh[a].father)
                    a 
            = hh[a].father;
                
            return a;
            }
            int unite(int x,int y)//返回的是樹的根節點
            {
                
            if(!x)            //x是空樹
                    return y;    //返回的就是y樹的根節點
                if(!y)
                    
            return x;
                
            if(hh[x].pow < hh[y].pow)            //以x樹主樹,y插入
                    x^=y^=x^=y;
                hh[x].right 
            = unite(hh[x].right,y);    //合并y和x的右子樹
                hh[ hh[x].right ].father = x;        //x的右子樹的父親是x(這不是廢話嘛)
                if(hh[ hh[x].left ].deep < hh[ hh[x].right ].deep)//保證左子深度要比右子樹大
                    hh[x].left ^= hh[x].right ^= hh[x].left ^= hh[x].right;
                hh[x].deep 
            = hh[ hh[x].right ].deep + 1;
                
            return x;
            }
            int maxpow(int k)//返回的是樹的根節點
            {
                
            int l,r;
                hh[k].pow 
            >>= 1;
                l 
            = hh[k].left;
                r 
            = hh[k].right;//節點單獨拿出來
                hh[l].father = l;
                hh[r].father 
            = r;//左右兒子分別成樹
                hh[k].left = hh[k].right = hh[k].deep = 0;//變成沒有左右兒子
                l = unite(l,r);//合并原來的左右兒子
                k = unite(l,k);//把這個節點加進合并出來的樹
                return k;
            }
            int main()
            {
                
            int n,i,m,a,b,x,y,k;
                
            while(scanf("%d",&n)==1)
                {
                    
            for(i=1;i<=n;i++)
                    {
                        scanf(
            "%d",&hh[i].pow);
                        hh[i].father 
            = i;
                        hh[i].left 
            = hh[i].right = hh[i].deep = 0;
                    }
                    scanf(
            "%d",&m);
                    
            while(m--)
                    {
                        scanf(
            "%d%d",&a,&b);
                        x 
            = find(a);//找根節點
                        y = find(b);//找根節點
                        if(x==y)
                            puts(
            "-1");
                        
            else
                        {
                            x 
            = maxpow(x);//處理x的根節點,并返回處理后的根節點
                            y = maxpow(y);
                            k 
            = unite(x,y);//合并兩顆樹
                            printf("%d\n",hh[k].pow);
                        }
                    }
                }
                
            return 0;
            }



            合并的時候的步驟
            0.其中一顆樹為空的話返回另外一個
            1.將x確定為主樹(交換xy)
            2.合并x的右兒子和y
            3.合并出來的根節點的father指向x
            4.保證左兒子深度大于右兒子

            還有一道:
            http://acm.hdu.edu.cn/showproblem.php?pid=1434
            posted on 2009-03-18 18:14 shǎ崽 閱讀(1057) 評論(0)  編輯 收藏 引用
            一日本道伊人久久综合影| 亚洲美日韩Av中文字幕无码久久久妻妇 | 漂亮人妻被中出中文字幕久久 | 久久综合色之久久综合| 久久免费视频一区| 久久国产精品成人影院| 久久er国产精品免费观看8| 久久青青草视频| 99久久国产亚洲高清观看2024| 久久久久久久久久久免费精品| 午夜天堂av天堂久久久| 2020最新久久久视精品爱| 久久天天躁狠狠躁夜夜躁2014| 狠狠狠色丁香婷婷综合久久俺| 香蕉99久久国产综合精品宅男自| 精品久久久久久成人AV| 色婷婷久久综合中文久久一本| 精品无码久久久久久尤物| 亚洲午夜无码久久久久小说| 国产精品久久久久9999高清| 久久久黄色大片| 久久99精品九九九久久婷婷| 91精品国产综合久久久久久| 久久久久久国产精品无码下载| 国产精品99久久精品爆乳| 97久久超碰成人精品网站| 伊人久久久AV老熟妇色| 亚洲欧洲精品成人久久奇米网| 99精品久久久久久久婷婷| 久久91精品国产91久久户| 国产成人久久AV免费| 久久A级毛片免费观看| 色狠狠久久AV五月综合| 亚洲国产欧洲综合997久久| 久久无码高潮喷水| 久久亚洲精品无码aⅴ大香| 人妻中文久久久久| 国产精品亚洲综合久久 | 中文字幕无码久久精品青草| 热久久国产欧美一区二区精品| 欧美久久久久久精选9999|