從ZOJ2114（Transportation Network）到Link-cut-tree（LCT）

来源:http://www.cnblogs.com/Onlynagesha/archive/2016/04/23/5425209.html
-Advertisement-
Play Games

【首先聲明：LCT≠動態樹，前者是一種數據結構，而後者是一類問題，即：LCT—解決—>動態樹】 Link-cut-tree（下文統稱LCT）是一種強大的數據結構，不僅可以像樹鏈剖分一樣對樹上的兩點進行詢問（權值和、權值的最值……），還可以維護森林的連通性。 學習LCT首推楊哲神犇的《QTREE解法的 ...


【首先聲明：LCT≠動態樹，前者是一種數據結構，而後者是一類問題，即：LCT—解決—>動態樹】

Link-cut-tree（下文統稱LCT）是一種強大的數據結構，不僅可以像樹鏈剖分一樣對樹上的兩點進行詢問（權值和、權值的最值……），還可以維護森林的連通性。

學習LCT首推楊哲神犇的《QTREE解法的一些研究》，很詳細地解釋了LCT的概念及實現

本文則以ZOJ2114一題為例，分析LCT實現過程中的一些事項，並且力求讀者對LCT有一個“不次於‘感性’的認識”

敘述過程中會直接引用論文中的術語

 

題目大意：

N個點（N<=2e4），M次操作（M<=4e4），維護N個點構成的森林

最初N個點兩兩不連通

U x y z：新建一條權值為z的邊，把x所在樹的根節點連到y所在的樹上

Q x y：詢問x到y的距離。如果x和y未連通，輸出Not connected.

 

思路：

對於Q操作，如果x和y所屬的根節點不同，那麼x和y必然是不連通的

對於U操作，首先需要找到x和y的根節點（分別記作u和v），然後把u連到v上

查詢根節點可以用並查集

我們需要對森林進行修改（合併樹）及詢問操作，樹鏈剖分是無法勝任的（樹剖只能用於靜態樹），所以我們考慮LCT

 

我們用Splay維護Auxiliary Tree（如果不知道這是什麼，請看論文）：

 1 enum { Left=0,Right=1 };
 2 
 3 struct SplayNode;
 4 SplayNode* vir;
 5 
 6 struct SplayNode
 7 {
 8     int dist;
 9     int totDist;
10     bool isRoot;
11     SplayNode* parent;
12     SplayNode* child[2];
13 };

（為閱讀方便，分割代碼時作了一些修改）

vir的作用是代替空指針，從而免去很多不必要的判斷

SplayNode類的成員變數如下：

dist：在森林（原圖）中，該節點與父節點之間邊的權值。

totDist：Auxiliary Tree中，以該節點為根的子樹的dist之和

isRoot：該節點是否為所在Auxiliary Tree的根節點

child[]：該節點在Auxiliary Tree中的左右孩子。

parent：既可以是Auxiliary Tree內部的父節點，也可以是Auxiliary Tree整體的path-parent

（1）如果isRoot==false，那麼parent表示該節點在Auxiliary Tree中的父節點

（2）如果isRoot==true，那麼parent表示其所在Auxiliary Tree的path-parent，即其在森林中的父節點

也就是說，對於某個節點u，可能有多個節點以u為parent，但其中只有至多兩個與u構成Auxiliary Tree。在編程實現中，這是一個值得註意的問題

 

如圖，ABCDE構成森林中的一個連通分量，實線表示Preferred Child

 

相應的Auxiliary Tree（Series）。實線表示Preferred Child關係，虛線表示Path Parent關係

在Auxiliary Tree中，我們“隱式”地把節點的深度作為BST的關鍵字。也就是說，中序遍歷一棵Auxiliary Tree，得到的就是一條從上到下的Preferred Path鏈

（如果你不能理解從圖1到圖2的轉換，複習一下LCT的相關定義）

 

之後是Splay的一些操作（成員函數）：

 1     void init()
 2     {
 3         dist=totDist=0;
 4         isRoot=true;
 5         parent=child[0]=child[1]=vir;
 6     }
 7 
 8     void update()
 9     {
10         this->totDist =
11                 child[Left]->totDist+child[Right]->totDist+this->dist;
12     }
13 
14     void rotate(int dir)
15     //If dir==Right then rotate clockwise, else rotate counter-clockwise
16     {
17         if(parent==parent->parent->child[Left])
18             parent->parent->child[Left]=this;
19         else if(parent==parent->parent->child[Right])
20             parent->parent->child[Right]=this;
21 
22         parent->child[dir^1]=this->child[dir];
23         child[dir]->parent=this->parent;
24 
25         child[dir]=parent;
26         parent=parent->parent;
27         child[dir]->parent=this;
28     }
29 
30     void zigzig(int dir)
31     {
32         parent->rotate(dir);
33         this->rotate(dir);
34 
35         child[dir]->child[dir]->update();
36         child[dir]->update();
37         this->update();
38     }
39 
40     void zigzag(int dir) //dir depends on first rotation
41     {
42         rotate(dir);
43         rotate(dir^1);
44 
45         child[Left]->update();
46         child[Right]->update();
47         this->update();
48     }
49 
50     void zig(int dir)
51     {
52         rotate(dir);
53         child[dir]->update();
54         this->update();
55     }
56 
57     void splay()
58     {
59         while(!isRoot)
60         {
61             int status=0;
62             if(this==parent->child[Left]) status|=1;
63             else status|=2;
64 
65             if(!parent->isRoot)
66             {
67                 if(parent->parent->isRoot) this->isRoot=true;
68                 if(parent==parent->parent->child[Left]) status|=4;
69                 else status|=8;
70             }
71             else
72                 this->isRoot=true;
73 
74             switch(status)
75             {
76             case 1: zig(Right);
77                     child[Right]->isRoot=false;
78                     break;
79             case 2: zig(Left);
80                     child[Left]->isRoot=false;
81                     break;
82             case 5: zigzig(Right);
83                     if(isRoot) child[Right]->child[Right]->isRoot=false;
84                     break;
85             case 6: zigzag(Left);
86                     if(isRoot) child[Right]->isRoot=false;
87                     break;
88             case 9: zigzag(Right);
89                     if(isRoot) child[Left]->isRoot=false;
90                     break;
91             case 10:zigzig(Left);
92                     if(isRoot) child[Left]->child[Left]->isRoot=false;
93                     break;
94             default:break;
95             }
96         }
97     }

 

各函數的說明：

init：初始化。令該節點成為獨立的一個連通分量。

update：（在旋轉以後）更新節點的totDist值。

rotate：將節點上旋。如果dir==Right，那麼沿順時針方向上旋；如果dir==Left，那麼沿逆時針方向上旋。

zig，zigzig，zigzag：Splay的單雙旋

splay：提根，將當前節點提到所在Auxiliary Tree的根部

 

 

17         if(parent==parent->parent->child[Left])
18             parent->parent->child[Left]=this;
19         else if(parent==parent->parent->child[Right])
20             parent->parent->child[Right]=this;

這裡的判斷需要特別註意。必須寫成else if的形式（還記得我們是怎樣定義parent的嗎？）

另外splay的過程中涉及到isRoot的變化

除此之外其他的部分和普通的SplayTree大同小異，在這裡就不多說了，詳見代碼。

 

至此，LCT的基礎——SplayNode就已經打好了，接下來就是LCT的精華：Access（也有的版本稱為Expose）操作：

 1 int access(SplayNode* u)
 2 {
 3     SplayNode* v=vir;
 4     int res=0;
 5     while(u!=vir)
 6     {
 7         u->splay();
 8         u->child[Right]->isRoot=true;
 9         res=u->child[Right]->totDist;
10         u->child[Right]=v;
11         v->isRoot=false;
12         u->update();
13         v=u; u=u->parent;
14     }
15     return res + v->child[Right]->totDist;
16 }
17 
18 inline int query(SplayNode* u,SplayNode* v)
19 {
20     access(u);
21     return access(v);
22 }

比起SplayNode的實現是不是短了許多？（斜眼笑

然而，正所謂濃縮就是精華，Access的原理可以說是不容小視的（畢竟是LCT所有操作的基石）

接下來我們以此圖（以下稱為原圖）為例，演示access（H）的全過程。圖為access（H）之前

access（H）之後的效果圖，可以看到途經的所有節點，其原來的Preferred Path都被切斷了，取而代之的是“直達”H的Preferred Path

access（H）之前的Auxiliary Tree，也是我們操作的對象。

首先我們splay（H），把H提到所在Auxiliary Tree的根部

此時H的右子樹對應原圖中的Preferred Path

由於新的Preferred Path要“切斷”沿途所有舊的Preferred Child，而H的右子樹對應H原來的Preferred Child

所以H和I之間要斷開，表示新的Preferred Path到H就中止了，以I為根的子樹成為一棵新的Auxiliary Tree

之後別忘了update一下H的totDist

為了將A和H用Preferred Path相連，我們還要對H的Path Parent，也就是對C“開刀”

首先還是splay（C）。當然C已經是Auxiliary Tree的根節點了，所以對於本例，splay（C）什麼都沒做

然後依然將C與右子樹D斷開。

之後，我們要將C的Auxiliary Tree與H的Auxiliary Tree相連。由於H的Auxiliary Tree在原圖中處於C的下方，所以H應該成為C的新的右孩子

如圖所示，A和E已經用Preferred Path相連了。至此access（H）過程已經完成。不妨把此時的Auxiliary Tree和上面的效果圖對比一下

當然在編程時我們需要一個判斷條件：C的parent為vir，再往上走就沒有任何意義了，所以access操作停止

 

……

 

那麼，access的返回值是幹嘛的？totDist到底有什麼卵用？

舉個慄子：詢問D到H的距離。我們已經進行了access（H）

我們給每條邊賦予一個權值（圖中用黑色標註）

但在LCT的Auxiliary Tree中，這個權值實際上是存儲到“下方”的節點中的（圖中以紅色標註）。括弧中是totDist，括弧外是dist

然後我們access（D）

這是access（D）之後的Auxiliary Tree

在原圖中，D到F的距離可以分解成D到C的距離和C到H的距離。之所以選擇C是因為C是D和F的最近公共祖先（LCA）

而在Auxiliary Tree中，這恰好對應C的新、舊右孩子的totDist之和

H是C的”舊“右孩子，被D取代後，D就成了C的”新“右孩子

在編程過程中，我們需要設法保存”舊“右孩子的totDist值（要不然就失聯了(￣▽￣")），access函數中的res變數恰好勝任了這一要求

query函數中進行了兩次access操作，第一次的返回值因為沒有意義所以被丟棄了，而第二次的返回值就是詢問的結果

 

問題已經解決了一半，接下來就是兩個子樹的合併（並不難）：

 1 const int maxN=20005;
 2 int center[maxN];
 3 
 4 int getCenter(int x)
 5 {
 6     return center[x]==x ? x :
 7            center[x]=getCenter(center[x]);
 8 }
 9 
10 inline void link(int u,int v,int len)
11 {
12     access(node+u);
13     node[u].splay();
14     center[u]=v;
15     node[u].parent=node+v;
16     node[u].dist=len;
17     node[u].update();
18 }

center就是並查集，合併之前，首先要用getCenter函數找到兩棵樹的根節點u和v，然後把u連到v上

首先access（u），然後splay（u）

splay的目的是讓u的parent成為vir，這樣在連接u和v時，不會切斷u所在的Auxiliary Tree

 

於是這道題用LCT完美解決（而且效率很高），附上完整代碼：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 
  5 enum { Left=0,Right=1 };
  6 
  7 struct SplayNode;
  8 SplayNode* vir;
  9 
 10 struct SplayNode
 11 {
 12     int dist;
 13     int totDist;
 14     bool isRoot;
 15     SplayNode* parent;
 16     SplayNode* child[2];
 17 
 18     void init()
 19     {
 20         dist=totDist=0;
 21         isRoot=true;
 22         parent=child[0]=child[1]=vir;
 23     }
 24 
 25     void update()
 26     {
 27         this->totDist =
 28                 child[Left]->totDist+child[Right]->totDist+this->dist;
 29     }
 30 
 31     void rotate(int dir)
 32     //If dir==Right then rotate clockwise, else rotate counter-clockwise
 33     {
 34         if(parent==parent->parent->child[Left])
 35             parent->parent->child[Left]=this;
 36         else if(parent==parent->parent->child[Right])
 37             parent->parent->child[Right]=this;
 38 
 39         parent->child[dir^1]=this->child[dir];
 40         child[dir]->parent=this->parent;
 41 
 42         child[dir]=parent;
 43         parent=parent->parent;
 44         child[dir]->parent=this;
 45     }
 46 
 47     void zigzig(int dir)
 48     {
 49         parent->rotate(dir);
 50         this->rotate(dir);
 51 
 52         child[dir]->child[dir]->update();
 53         child[dir]->update();
 54         this->update();
 55     }
 56 
 57     void zigzag(int dir) //dir depends on first rotation
 58     {
 59         rotate(dir);
 60         rotate(dir^1);
 61 
 62         child[Left]->update();
 63         child[Right]->update();
 64         this->update();
 65     }
 66 
 67     void zig(int dir)
 68     {
 69         rotate(dir);
 70         child[dir]->update();
 71         this->update();
 72     }
 73 
 74     void splay()
 75     {
 76         while(!isRoot)
 77         {
 78             int status=0;
 79             if(this==parent->child[Left]) status|=1;
 80             else status|=2;
 81 
 82             if(!parent->isRoot)
 83             {
 84                 if(parent->parent->isRoot) this->isRoot=true;
 85                 if(parent==parent->parent->child[Left]) status|=4;
 86                 else status|=8;
 87             }
 88             else
 89                 this->isRoot=true;
 90 
 91             switch(status)
 92             {
 93             case 1: zig(Right);
 94                     child[Right]->isRoot=false;
 95                     break;
 96             case 2: zig(Left);
 97                     child[Left]->isRoot=false;
 98                     break;
 99             case 5: zigzig(Right);
100                     if(isRoot) child[Right]->child[Right]->isRoot=false;
101                     break;
102             case 6: zigzag(Left);
103                     if(isRoot) child[Right]->isRoot=false;
104                     break;
105             case 9: zigzag(Right);
106                     if(isRoot) child[Left]->isRoot=false;
107                     break;
108             case 10:zigzig(Left);
109                     if(isRoot) child[Left]->child[Left]->isRoot=false;
110                     break;
111             default:break;
112             }
113         }
114     }
115 };
116 
117 int access(SplayNode* u)
118 {
119     SplayNode* v=vir;
120     int res=0;
121     while(u!=vir)
122     {
123         u->splay();
124         u->child[Right]->isRoot=true;
125         res=u->child[Right]->totDist;
126         u->child[Right]=v;
127         v->isRoot=false;
128         u->update();
129         v=u; u=u->parent;
130     }
131     return res + v->child[Right]->totDist;
132 }
133 
134 inline int query(SplayNode* u,SplayNode* v)
135 {
136     access(u);
137     return access(v);
138 }
139 
140 void initVir()
141 {
142     vir=new SplayNode;
143     vir->init();
144 }
145 
146 const int maxN=20005;
147 
148 SplayNode node[maxN];
149 int center[maxN];
150 int N,Q;
151 int lastRes=0;
152 
153 inline void link(int u,int v,int len)
154 {
155     access(node+u);
156     node[u].splay();
157     center[u]=v;
158     node[u].parent=node+v;
159     node[u].dist=len;
160     node[u].update();
161 }
162 
163 inline void initNode()
164 {
165     for(int i=1;i<=N;i++) node[i].init();
166     for(int i=1;i<=N;i++) center[i]=i;
167 }
168 
169 int getCenter(int x)
170 {
171     return center[x]==x ? x :
172            center[x]=getCenter(center[x]);
173 }
174 
175 #define DEBUG
176 #undef DEBUG
177 
178 #ifdef DEBUG
179 int qc=0;
180 #endif
181 
182 void solve()
183 {
184     lastRes=0;
185     scanf("%d%d",&N,&Q);
186     initNode();
187     char cmd;
188     int v1,v2,len;
189     while(Q--)
190     {
191         do cmd=getchar(); while(cmd==' ' || cmd=='\n');
192         if(cmd=='Q')
193         {
194             scanf("%d%d",&v1,&v2);
195             if(getCenter(v1)==getCenter(v2))
196                 printf("%d\n",lastRes=query(node+v1,node+v2));
197             else printf("Not connected.\n");
198 #ifdef DEBUG
199             printf("#%d query successful.\n",++qc);
200 #endif
201         }
202         else
203         {
204             scanf("%d%d%d",&v1,&v2,&len);
205 #ifndef DEBUG
206             v1=(v1-lastRes-1)%N;
207             if(v1<=0) v1+=N;
208             v2=(v2-lastRes-1)%N;
209             if(v2<=0) v2+=N;
210 #endif
211             link(getCenter(v1),getCenter(v2),len);
212         }
213     }
214 }
215 
216 int main()
217 {
218     initVir();
219     int X; scanf("%d",&X);
220     while(X--) solve();
221     return 0;
222 }
Problem：ZOJ P2114

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 為什麼要用枚舉實現Singleton--java
    為什麼要用枚舉實現Singleton java 理由一：無需再考慮可序列化的情況   《effective java》第77條：對於實例控制，枚舉類型優先於readResolve   說到readResolve，有的人可能會不甚清楚其作用,簡單來說，readR ...
  • Hibernate註解----關聯映射註解以及課程總結詳解----圖片版本
    上一篇，記錄了Hibernate註解 類級別註解以及屬性註解詳解 ，我們這一節主要講解的是Hibernate註解 關聯映射註解以及課程總結詳解。 本節的主要內容： 第3章 關聯映射註解 3-1 本章簡介 3-2 實體之間的關係 3-3 一對一單向外鍵關聯(一) 3-4 一對一單向外鍵關聯(二) 3- ...
  • Java中處理異常throw和throws
    1.首先我們來瞭解什麼是異常呢？ 異常阻止當前方法或作用域繼續執行的問題。 2.處理異常 說到處理異常，我們當然會想到 try catch finally 在java中我們會對異常的處理有更高的認識 我們會學習 throw throws等更好的處理異常 3.throw關鍵字：語句拋出異常 throw ...
  • Typecho博客發佈文章同步新浪微博插件
    本文章向碼農介紹Typecho博客發佈文章同步新浪微博插件，這樣做能夠增加你博客的社會化流量，同時增加用戶的粘性。感興趣的碼農可以參考一下。 Typecho博客發佈文章同步新浪微博插件，能夠增加你博客的社會化流量，同時增加用戶的粘性，點擊下載： Typechosina.zip 安裝教程如下： 激活後 ...
  • Tomcat下載和安裝
    Tomcat 是一個免費的開放源代碼的 Servlet 容器，它是 Apache 軟體基金會的一個頂級項目，由 Apache，Sun和其他一些公司及個人共同開發而成。由於有了 Sun 的參與與支持，最新的 Servlet 和 JSP 規範總是能在 Tomcat 中的到體現。 官方網站：http:// ...
  • java包（package）的命名規範
    Java的包名都有小寫單片語成，類名首字母大寫；包的路徑符合所開發的 系統模塊的 定義，比如生產對生產，物資對物資，基礎類對基礎類。以便看了包名就明白是哪個模塊，從而直接到對應包里找相應的實現。 由於Java面向對象的特性，每名Java開發人員都可以編寫屬於自己的Java Package，為了保障每 ...
  • super關鍵字、final關鍵字
    ...
  • Java this的一兩點使用
    Java this的一兩點使用 之前的文章都是關於Android的使用，這次想寫一些關於Java的知識，總結一下Java的使用。這次寫的是關於Java this的使用，介紹以下內容： 1. this的概念 2. this的各種應用 3. 總結 this 是什麼 在寫一個方法的時候，如果想在方法內部獲 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類