نظریه گراف‌ها برای المپیاد کامپیوتر
  • Basic Definitions
    • Introduction to Graphs and Graph Modeling
    • Types of Graphs
    • Graph Implementation
    • Walks, Trails, Paths, Extremal
    • Subgraphs
    • Connectivity, Cut Edge, and Cut Vertex
    • Bipartite Graph
  • Trees
    • Introductory Properties
    • Distance in Tree and Graph
    • Counting the Number of Trees
    • DFS
    • BFS
    • Algorithm for Finding Tree Diameter
    • DFS Start/Finish Time
    • Cut Vertex and Bridge Algorithms
    • Idea Cultivation Workshop
  • Directed Graph
    • Definitions
    • Tournament
    • Directed Acyclic Graph
    • Strongly Connected Components
    • Detecting Cycles in a Directed Graph
    • Games and Directed Graphs
    • Functional Graphs and Permutation Graphs
  • Proof Techniques for Graph Problems
    • Extremal Choices
    • Contracting
    • Graph and Magic
  • Eulerian Tour and Hamiltonian Cycle
    • Introduction
    • Eulerian Tour in Directed and Undirected Graphs
    • De Bruijn sequence
    • Existence Theorems for Hamiltonian Cycles
    • Exponential Algorithms for Finding Hamiltonian Cycles and Paths
  • Shortest Path Algorithms
    • Bellman-Ford
    • Dijkstra
    • Floyd-Warshall
  • Matrices
    • Matrices and Operations on Them
    • Determinants of Matrices
    • Incidence Matrix
    • Adjacency Matrix
    • Number of Walks of Length n
    • Obtaining Recursive Functions Using Graphs and Matrices
  • Tree Data Structures
    • Binary Tree
    • Binary Search Tree (BST)
    • Heap
    • DSU
    • Segment Tree
    • Trie
  • NP and NP-complete Problems
    • NP and NP-complete Definitions
    • Proof of NP-Completeness of the SAT Problem
    • Graph NP-Complete Problems
  • Lca
    • Problem Description
    • O(n+q*lg(n)) Solution using Heavy-Light Decomposition
    • Tarjan's Offline Algorithm
    • Relationship between LCA and RMQ
    • LCA Linear Time Solution
    • Virtual Tree
  • Advanced Tree Algorithms
    • Minimum Spanning Tree
    • Sack
    • Centroid
    • Huffman Coding
    • Tree Hashing
    • Heavy-Light Decomposition (HLD)
  • Connectivity
    • Cuts and Connectivity
    • k-connected Graph
    • Max-Flow Min-Cut
  • Matching
    • Introduction
    • Matching in Bipartite Graphs
    • Min-Max Theorems
    • Applications
    • Maximum Flow and Matching
    • Poset
    • Matching in General Graphs
  • Special Topics
    • Planar Graph
    • Degree Sequence
    • Coloring
    • Identical Graphs
    • Random Walk
    • Ramsey Numbers
    • Independent Set and Clique
    • 2-SAT
    • Several Special Matrices
  • Appendix
    • How to Use This Book?
    • Introduction to Algorithms and Complexity
    • Cheat Sheet
  Index      Lca  Problems  Change Language (Farsi)   Source

Lca¶

  • Problem Description
    • Ancestor at Specific Height Problem
    • Lowest Common Ancestor Problem
    • Relationship Between These Two Problems
  • O(n+q*lg(n)) Solution using Heavy-Light Decomposition
    • Heavy-Light Decomposition
      • Number of light edges on the path to the root
    • Solving the problem of ancestor at a specific height
    • Solving the LCA Problem
  • Tarjan's Offline Algorithm
    • Solution for the K-th Ancestor Problem
    • Solution for the LCA Problem
  • Relationship between LCA and RMQ
    • Converting RMQ to LCA
      • Linear-Time Cartesian Tree Construction
    • Converting LCA to RMQ
    • Solving RMQ with Sparse Table
  • LCA Linear Time Solution
  • Virtual Tree
    • Why is the Virtual Tree important to us?
      • First Problem
      • Diameter of a Subset
    • Algorithm
      • Introduction
      • First Attempt
      • A Better Algorithm
      • Optimal Order?
      • Implementation
  Previous Next  

This book is made by The Shaazzz contributors.

It is publicly available with cc-by-sa license.

Last updated at اکتبر 13, 2025.

Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).