euler tour vnoi

• Interview Problems on Tree
• Practice Tree
• MCQs on Tree
• Tutorial on Tree
• Types of Trees
• Basic operations
• Tree Traversal
• Binary Tree
• Complete Binary Tree
• Ternary Tree
• Binary Search Tree
• Red-Black Tree
• Full Binary Tree
• Advantages & Disadvantages

Euler Tour of Tree

A Tree is a generalization of connected graph where it has N nodes that will have exactly N-1 edges, i.e one edge between every pair of vertices. Find the Euler tour of tree represented by adjacency list.

Input :   

Output : 1 2 3 2 4 2 1

Output : 1 5 4 2 4 3 4 5 1

Euler tour is defined as a way of traversing tree such that each vertex is added to the tour when we visit it (either moving down from parent vertex or returning from child vertex). We start from root and reach back to root after visiting all vertices. It requires exactly 2*N-1 vertices to store Euler tour.

Approach : We will run DFS(Depth first search) algorithm on Tree as:   

• Visit root node, i.e 1   vis[1]=1, Euler[0]=1  run dfs() for all unvisited adjacent nodes(2) 
• Visit node 2   vis[2]=1, Euler[1]=2  run dfs() for all unvisited adjacent nodes(3, 4) 
• Visit node 3   vis[3]=1, Euler[2]=3  All adjacent nodes are already visited, return to parent node  and add parent to Euler tour Euler[3]=2 
• Visit node 4   vis[4]=1, Euler[4]=4  All adjacent nodes are already visited, return to parent node  and add parent to Euler tour, Euler[5]=2 
• Visit node 2   All adjacent nodes are already visited, return to parent node  and add parent to Euler tour, Euler[6]=1 
• Visit node 1   All adjacent nodes are already visited, and node 1 is root node  so, we stop our recursion here. 

Similarly, for example 2:   

Implementation:

Complexity Analysis:

• Auxiliary Space: O(N) 
• Time Complexity: O(N)

Please Login to comment...

Similar reads.

• Top Android Apps for 2024
• Top Cell Phone Signal Boosters in 2024
• Best Travel Apps (Paid & Free) in 2024
• The Best Smart Home Devices for 2024
• 15 Most Important Aptitude Topics For Placements [2024]

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Table of Contents

Link cut tree.

Author s : Benjamin Qi, Neo Wang, Gabriel Xu

Dynamic operations on a rooted forest

Prerequisites

• Advanced - Offline Deletion
• Advanced - Treaps

A splay tree is a type of self-balancing binary search tree that supports efficient implementation of operations such as finding an element, deleting an element, splitting a tree, and joining two trees.

When a node in a splay tree is accessed, a splay operation is performed on the node that moves it to the root of the tree while also roughly balancing the tree.

Focus Problem – try your best to solve this problem before continuing!

A link cut tree is a data structure that uses splay trees to represent a forest of rooted trees and can perform the following operations with an amortized upper bound time complexity of O ( log ⁡ N ) \mathcal{O}(\log N) O ( lo g N ) :

• Linking a tree with a node by making the root of the tree a child of any node of another tree
• Deleting the edge between a node and its parent, detaching the node's subtree to make a new tree
• Find the root of the tree that a node belongs to

These operations all use the access ( v ) \texttt{access}(v) access ( v ) subroutine, which creates a preferred path from the root of the represented tree to vertex v v v , making a corresponding auxiliary splay tree with v v v as the root.

With Link Cut Tree

We can use a link cut tree to process each type of query O ( log ⁡ N ) \mathcal{O}(\log N) O ( lo g N ) time. Adding an edge or removing an edge between two vertices are standard features of the link cut tree.

Checking if there's a path between two nodes is the same as checking if they're part of the same tree. To check if two nodes are part of the same tree, we can check if the roots of the trees of the two nodes are the same.

Implementation

With euler tour tree.

An alternative solution is to use the Euler Tour Tree (ETT) technique, which builds upon our existing Euler tour technique by storing the Euler Tour of the tree in a balanced binary search tree instead of an array.

Finding Connectivity

The link cut tree can be used to solve problems that deal with queries updating trees and querying for connectivity.

Explanation

The lowest common ancestor of two nodes is found by first making a preferred path from the root to one node and then the other. After we splay the first node, the lowest common ancestor is just the first node's parent.

Time Complexity: O ( N log ⁡ N ) \mathcal{O}(N\log N) O ( N lo g N )

Link Cut Tree - Paths

An LC Tree can also calculate the aggregate (max, min, sum, etc.) of the weights of the edges or nodes on a path.

To do this, we can define a function that will return an aggregate for the path from the root of the tree to the provided vertex. We can augment the auxiliary splay trees with the value(s) we want to keep track of. The aggregate for the path from the root of a tree to a vertex can be found by retrieving the value(s) from the splay tree created after accessing the vertex.

Time Complexity: O ( Q log ⁡ N ) \mathcal{O}(Q\log N) O ( Q lo g N )

Link Cut Tree - Subtrees

We can also maintain information about subtrees by keeping track of values for the virtual subtrees of a node. When querying for information such as the subtree sum, we call access on the node so that all of its children in the represented tree are part of virtual subtrees and then retrieve the desired value.

Module Progress : Not Started

Join the usaco forum.

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

• Lowest Common Ancestor - Binary Lifting
• Lowest Common Ancestor - Farach-Colton and Bender algorithm
• Solve RMQ by finding LCA
• Lowest Common Ancestor - Tarjan's off-line algorithm

Lowest Common Ancestor - $O(\sqrt{N})$ and $O(\log N)$ with $O(N)$ preprocessing ¶

Given a tree $G$ . Given queries of the form $(v_1, v_2)$ , for each query you need to find the lowest common ancestor (or least common ancestor), i.e. a vertex $v$ that lies on the path from the root to $v_1$ and the path from the root to $v_2$ , and the vertex should be the lowest. In other words, the desired vertex $v$ is the most bottom ancestor of $v_1$ and $v_2$ . It is obvious that their lowest common ancestor lies on a shortest path from $v_1$ and $v_2$ . Also, if $v_1$ is the ancestor of $v_2$ , $v_1$ is their lowest common ancestor.

The Idea of the Algorithm ¶

Before answering the queries, we need to preprocess the tree. We make a DFS traversal starting at the root and we build a list $\text{euler}$ which stores the order of the vertices that we visit (a vertex is added to the list when we first visit it, and after the return of the DFS traversals to its children). This is also called an Euler tour of the tree. It is clear that the size of this list will be $O(N)$ . We also need to build an array $\text{first}[0..N-1]$ which stores for each vertex $i$ its first occurrence in $\text{euler}$ . That is, the first position in $\text{euler}$ such that $\text{euler}[\text{first}[i]] = i$ . Also by using the DFS we can find the height of each node (distance from root to it) and store it in the array $\text{height}[0..N-1]$ .

So how can we answer queries using the Euler tour and the additional two arrays? Suppose the query is a pair of $v_1$ and $v_2$ . Consider the vertices that we visit in the Euler tour between the first visit of $v_1$ and the first visit of $v_2$ . It is easy to see, that the $\text{LCA}(v_1, v_2)$ is the vertex with the lowest height on this path. We already noticed, that the LCA has to be part of the shortest path between $v_1$ and $v_2$ . Clearly it also has to be the vertex with the smallest height. And in the Euler tour we essentially use the shortest path, except that we additionally visit all subtrees that we find on the path. But all vertices in these subtrees are lower in the tree than the LCA and therefore have a larger height. So the $\text{LCA}(v_1, v_2)$ can be uniquely determined by finding the vertex with the smallest height in the Euler tour between $\text{first}(v_1)$ and $\text{first}(v_2)$ .

The tour starting at vertex $6$ and ending at $4$ we visit the vertices $[6, 2, 1, 3, 1, 4]$ . Among those vertices the vertex $1$ has the lowest height, therefore $\text{LCA(6, 4) = 1}$ .

To recap: to answer a query we just need to find the vertex with smallest height in the array $\text{euler}$ in the range from $\text{first}[v_1]$ to $\text{first}[v_2]$ . Thus, the LCA problem is reduced to the RMQ problem (finding the minimum in an range problem).

Using Sqrt-Decomposition , it is possible to obtain a solution answering each query in $O(\sqrt{N})$ with preprocessing in $O(N)$ time.

Using a Segment Tree you can answer each query in $O(\log N)$ with preprocessing in $O(N)$ time.

Since there will almost never be any update to the stored values, a Sparse Table might be a better choice, allowing $O(1)$ query answering with $O(N\log N)$ build time.

Implementation ¶

In the following implementation of the LCA algorithm a Segment Tree is used.

Practice Problems ¶

• SPOJ: DISQUERY
• TIMUS: 1471. Distance in the Tree
• CODEFORCES: Design Tutorial: Inverse the Problem
• CODECHEF: Lowest Common Ancestor
• SPOJ - Lowest Common Ancestor
• SPOJ - Ada and Orange Tree
• DevSkill - Motoku (archived)
• UVA 12655 - Trucks
• Codechef - Pishty and Tree
• UVA - 12533 - Joining Couples
• Codechef - So close yet So Far
• Codeforces - Drivers Dissatisfaction
• UVA 11354 - Bond
• SPOJ - Querry on a tree II
• Codeforces - Best Edge Weight
• Codeforces - Misha, Grisha and Underground
• SPOJ - Nlogonian Tickets
• Codeforces - Rowena Rawenclaws Diadem
• Manuel Pineda (42.36%)
• Jakob Kogler (31.94%)
• Morass (8.33%)
• Anthony (6.94%)
• Sunil Sangwan (4.86%)
• Oleksandr Kulkov (2.08%)
• Gabriel Silva Simões (2.08%)
• Gaurang Tandon (1.38%)

¶ Heavy-Light Decomposition (HLD)

• Phạm Hoàng Hiệp – University of Georgia
• Nguyễn Minh Hiển - Trường Đại học Công Nghệ, ĐHQGHN
• Nguyễn Minh Nhật - Trường THPT chuyên Khoa học Tự nhiên, ĐHQGHN
• Đặng Đoàn Đức Trung - UT Austin

¶ Giới thiệu về HLD

Heavy-Light Decomposition (HLD) , dịch ra tiếng Việt là phân chia nặng nhẹ là một kỹ thuật thường được dùng trong những bài toán xử lý trên cây.

Trong bài viết này, để ngắn gọn và dễ nhớ, chúng ta sẽ gọi tên kỹ thuật là HLD .

Tuy nghe tên có vẻ kinh khủng nhưng trên thực tế, đây là một kỹ thuật có ý tưởng khá tự nhiên và có tính ứng dụng cao, có thể được sử dụng trong nhiều bài tập.

¶ Kiến thức cần biết

• Các thuật toán duyệt đồ thị cơ bản (DFS, BFS, ...)
• Lowest Common Ancestor (LCA) - Tổ tiên chung gần nhất
• Segment Tree
• Euler tour on tree (nên biết nhưng không bắt buộc)

Để trả lời câu hỏi HLD sẽ giúp chúng ta làm gì, chúng ta sẽ cùng giải một bài toán.

Trước hết, chúng ta sẽ đến với phiên bản dễ hơn của bài toán như sau.

Cho một mảng số nguyên dương gồm tối đa phần tử. Chúng ta cần xử lý tối đa truy vấn thuộc một trong hai loại sau:

• Cập nhật giá trị của phần tử thứ thành
• Tính tổng XOR của tất cả các phần tử trong đoạn từ đến

Bài toán trên là một bài toán quen thuộc và có thể được xử lý đơn giản bằng cách sử dụng Segment Tree. Nhưng, giả sử thay vì mảng một chiều, chúng ta cần xử lý bài toán trên cây thì phải làm như thế nào?

¶ Phát biểu bài toán

Bạn đọc có thể đọc đề bài cụ thể và nộp code tại đây

Cho một cây (một đồ thị có đỉnh và cạnh và giữa hai đỉnh bất kỳ có đúng một đường đi giữa chúng). Mỗi đỉnh được gán một giá trị. Chúng ta cần xử lý hai loại truy vấn

• Cập nhật giá trị của đỉnh thành
• Tính tổng XOR của tất cả các giá trị trên đường đi từ đỉnh đến đỉnh

Đường đi từ đến trên đồ thị được định nghĩa là một chuỗi các đỉnh trong đó tồn tại một cạnh nối giữa và , và , ..., đến , đến . Với mỗi cặp đỉnh , bất kỳ trên cây tồn tại một và chỉ một đường đi từ đến .

¶ Ý tưởng chính

Vậy chính xác thì HLD sẽ làm gì để giúp chúng ta giải được phiên bản "trên cây" của bài toán trên? Liệu chúng ta có thể biến cây cho trước thành một mảng để giải bài toán trên đó? Câu trả lời là không. Tuy nhiên chúng ta có thể chia cây thành một số phần, và giải bài toán trên từng phần đó. Cụ thể như sau, giả sử có cây sau đây

Không mất tính tổng quát, có thể coi đỉnh là gốc của cây. Với mỗi đỉnh không phải lá trên cây, chúng ta sẽ đánh dấu những cạnh nối đỉnh đó với con có kích thước cây con lớn nhất của của nó.

Ví dụ, xét đỉnh có ba đỉnh con lần lượt là đỉnh , và . Cây con ở hai đỉnh và có kích thước là , còn cây con ở đỉnh có kích thước là .

Vì vậy, chúng ta sẽ đánh dấu cạnh nối giữa đỉnh và đỉnh (tô màu đỏ). Làm tương tự với các đỉnh còn lại, chúng ta được cây như hình vẽ dưới đây.

Chúng ta sẽ gọi những cạnh màu đỏ là những "cạnh nặng" (heavy edges) vì chúng nối một đỉnh với đỉnh con "nặng nhất" . Những cạnh còn lại sẽ được gọi là những "cạnh nhẹ" (light edges)

Có thể thấy rằng, những cạnh được đánh dấu sẽ tạo thành các "chuỗi" đi từ trên xuống dưới. Ví dụ như chuỗi hay chuỗi . Các đỉnh là lá cũng có thể coi là một chuỗi riêng.

Với cách quy ước trên, ta có thể thấy rằng hai chuỗi "liền nhau" được nối với nhau bởi một cạnh nhẹ. Hai chuỗi "liền nhau" là hai chuỗi mà tồn tại đỉnh nằm ở một chuỗi và nằm ở chuỗi còn lại sao cho và có cạnh nối trực tiếp với nhau. Do và khác chuỗi nên cạnh nối giữa và là cạnh nhẹ. Hai chuỗi không thể nối ở nhiều hơn một cặp điểm.

Khi đó, chúng ta có thể chứng minh được rằng đường đi giữa hai đỉnh bất kỳ trên cây đi qua không quá chuỗi. Bạn đọc có thể tự chứng minh nhận xét trên trước khi đọc chứng minh bên dưới.

Xét một đỉnh $v$ được nối với đỉnh cha của nó là $p$ bởi một cạnh nhẹ. Giả sử kích thước cây con của $v$ là $x$ và kích thước cây con của $p$ là $y$. Do cạnh nặng đi từ $p$ không được nối xuống $v$ nên chắc chắn tồn tại một con khác của $p$ là $u$ có kích thước cây con $\geq x$. Vì vậy, $y \geq 2 * x$

Do với mỗi lần nhảy qua cạnh nhẹ, kích thước của cây con ở đỉnh sau khi nhảy sẽ tăng ít nhất là gấp đôi nên ta có thể kết luận rằng để đi lên một tổ tiên bất kỳ ở phía trên thì có thể nhảy qua không quá cạnh nhẹ. Do mỗi lần đi qua cạnh nhẹ chính là một lần nhảy sang chuỗi mới nên từ một đỉnh lên tổ tiên bất kỳ của nó sẽ chỉ đi qua chuỗi.

Khi đó, từ hai đỉnh , bất kỳ, chúng ta có thể tìm LCA của , và đi từ , đến LCA. Số chuỗi đi qua sẽ không quá

Ngoài ra, nếu ta duyệt cây bằng DFS ưu tiên các đỉnh liền trong chuỗi trước , ta có thể nhận thấy là các đỉnh trên cùng một chuỗi sẽ nằm kế tiếp nhau trên thứ tự DFS, và vì thế việc truy vấn một đoạn con bất kì trên một chuỗi nào đó có thể được thực hiện trên Segment tree với độ phức tạp là .

Như vậy, chúng ta đi qua không quá chuỗi, với mỗi chuỗi chúng ta có thể thực hiện trả lời truy vấn hoặc update trong trên Segment tree nên độ phức tạp cho việc trả lời các truy vấn và cập nhật trên một đường đi giữa hai đỉnh bất kỳ trên cây là

¶ Chi tiết cài đặt

Thông thường, do việc sử dụng HLD sẽ đi kèm với một cấu trúc dữ liệu nào đó và duyệt đồ thị, code có thể sẽ dài và gồm nhiều phần. Tuy nhiên, nếu nắm chắc ý tưởng chính thì cài đặt HLD rất đơn giản.

¶ Tiền xử lý

Đầu tiên, ta cần phải tính kích thước của cây con từng đỉnh để lấy ra các con "nặng" của từng đỉnh một. Ngoài ra, ta cần tính thêm độ sâu các đỉnh để phục vụ cho thao tác tính LCA.

mảng và lần luợt lưu kích thuớc cây con, độ sâu và cha (tổ tiên trực tiếp) của các đỉnh trên cây mảng là mảng vector để lưu lại thông tin về đồ thị. là vector gồm các đỉnh kề với .

¶ Tìm cạnh nặng, cạnh nhẹ và tạo các chuỗi

Sau đó chúng ta thực hiện phân chia các đỉnh vào các chuỗi. Với mỗi đỉnh, cần lưu lại chuỗi của đỉnh và vị trí của đỉnh khi đặt các chuỗi liên tiếp với nhau (để thuận tiện cho việc xử lý truy vấn). Với mỗi chuỗi, chúng ta cần biết đỉnh đầu tiên của chuỗi (để thực hiện việc nhảy giữa các chuỗi).

là biến dùng để lưu lại đỉnh con "nặng nhất". là mảng dùng để lưu lại các chuỗi. là mảng lưu lại số thứ tự của các chuỗi. là mảng lưu lại node đầu tiên ( bé nhất) của từng chuỗi để biết khi nào cần nhảy sang chuỗi mới qua cạnh nhẹ. Mảng lưu lại vị trí của các đỉnh trên để tiện xử lý trên segment tree. và lần lượt là các biến lưu lại chỉ số của chuỗi và vị trí trong mảng để dùng cho chuỗi và đỉnh tiếp theo

Như vậy, với mỗi đỉnh, chúng ta sẽ tìm cạnh nặng và đi xuống cạnh đó trước. Sau đó, chúng ta sẽ lần lượt tạo ra các chuỗi mới và nhảy sang các đỉnh nhẹ. Như vậy, thứ tự duyệt đồ thị sẽ đảm bảo mỗi chuỗi được lưu đúng thứ tự từ trên xuống dưới trong một đoạn liên tiếp trên mảng .

Trong phần lớn các bài toán sử dụng HLD để thực hiện truy vấn trên đường đi, chúng ta cần tìm tổ tiên chung gần nhất và thực hiện thao tác lần lượt từ hai đỉnh đến tổ tiên chung này. Rất may là chúng ta có thể sử dụng chính những thông tin đã lưu để tìm ra LCA một cách nhanh chóng.

Khi nhảy từ một node qua một cạnh nhẹ lên cha của nó, chúng ta luôn nhảy sang một chuỗi có số thứ tự bé hơn (do thứ tự duyệt đồ thị trong hàm ) nên để tìm LCA của hai đỉnh, chúng ta sẽ tìm chuỗi chứa LCA đó.

Liên tục thực hiện nhảy từ chuỗi có số thứ tự lớn hơn lên một chuỗi có số thứ tự bé hơn (Để đảm bảo không bị nhảy quá, luôn chọn đỉnh đang ở chuỗi có số thứ tự lớn hơn để nhảy) cho đến khi hai đỉnh nằm trên cùng một chuỗi.

Ở đó, đỉnh có độ sâu thấp hơn là LCA của và .

¶ Segment tree

Duới đây là các thao tác xử lý trên segment tree. Phần này sẽ đủ để xử lý phiên bản không trên cây của bài toán.

¶ Các thao tác trên cây

Và cuối cùng, chúng ta sẽ có các hàm để xử lý truy vấn trên cây. Tất nhiên có thể đưa toàn bộ phần này vào trong main mà không tăng độ dài code. Tuy nhiên để dễ nhìn và tiện debug, chúng ta sẽ code riêng hàm để xử lý truy vấn trên đuờng đi từ đỉnh đến đỉnh .

Do bài toán chỉ yêu cầu cập nhật trên điểm nên hàm không có gì đáng chú ý. Độ phức tạp của hàm này là .

Hàm dùng để trả lời truy vấn tổng XOR của các số trên đường đi từ đến . Sau đó, chúng ta thực hiện chia đường đi này thành các đoạn trên các chain rồi thực hiện thao tác tính trên từng đoạn.

Có thể thấy, cách nhảy trong khi tính toán Query chính là cách nhảy khi tìm LCA. Trên thực tế, chúng ta không cần tìm LCA trước mà có thể thực hiện việc đó ngay khi tính Query. Nhưng trong bài này, phần tìm LCA được code riêng một hàm để dễ hiểu và tiện giải thích.

¶ Code đầy đủ

Dưới đây là code đầy đủ cho bài toán (kết hợp của tất cả các đoạn trên, khai báo biến và hàm main) để bạn đọc tham khảo. (Code nộp AC)

Bài viết trên được tham khảo từ bài viết gốc Hybrid Tutorial 1: Heavy-Light Decomposition . Bạn đọc có thể tham khảo và xem video hướng dẫn kèm theo của galen_colin. Ngoài ra có thể tham khảo bài viết của CP algo .

Trước hết, bạn đọc nên tự cài đặt và nộp bài tập phía trên tại đây . Sau đó có thể làm thêm các bài tập luyện tập dưới đây

• Path Queries (CSES)
• LUBENICA (SPOJ)
• QTREE (SPOJ)
• GRASSPLA (SPOJ)
• GSS7 (SPOJ)
• QRYLAND (CodeChef)
• MONOPLOY (CodeChef)
• QUERY (CodeChef)
• BLWHTREE (CodeChef)
• Milk Visits (USACO)
• Max Flow (USACO)
• Exercise Route (USACO)

• Preplanned tours
• Daytrips out of Moscow
• Themed tours
• Customized tours
• St. Petersburg

Moscow Metro

The Moscow Metro Tour is included in most guided tours’ itineraries. Opened in 1935, under Stalin’s regime, the metro was not only meant to solve transport problems, but also was hailed as “a people’s palace”. Every station you will see during your Moscow metro tour looks like a palace room. There are bright paintings, mosaics, stained glass, bronze statues… Our Moscow metro tour includes the most impressive stations best architects and designers worked at - Ploshchad Revolutsii, Mayakovskaya, Komsomolskaya, Kievskaya, Novoslobodskaya and some others.

What is the kremlin in russia?

The guide will not only help you navigate the metro, but will also provide you with fascinating background tales for the images you see and a history of each station.

And there some stories to be told during the Moscow metro tour! The deepest station - Park Pobedy - is 84 metres under the ground with the world longest escalator of 140 meters. Parts of the so-called Metro-2, a secret strategic system of underground tunnels, was used for its construction.

During the Second World War the metro itself became a strategic asset: it was turned into the city's biggest bomb-shelter and one of the stations even became a library. 217 children were born here in 1941-1942! The metro is the most effective means of transport in the capital.

There are almost 200 stations 196 at the moment and trains run every 90 seconds! The guide of your Moscow metro tour can explain to you how to buy tickets and find your way if you plan to get around by yourself.

Problem list

Problem search, hot problems.

• Bedao Regular Contest 20 - Đếm cặp