Subscribed unsubscribe Subscribe Subscribe

0w1

LCA

CFR 609 E. Minimum spanning tree for each edge ( LCA, Union Find, Kruskal )

Problem - 609E - Codeforces題意: 給一張圖,分別問每一條邊必須被選擇時的最小生成樹花費是多少。制約: N, M ≤ 2e5解法: 找出原圖的最小生成樹後,做倍增 LCA,同時紀錄向上的瓶頸( 最大 )權值。指定的邊若在原本的生成樹,直接輸出當前最小花費,否則…

HE Dexter's Random Generator ( LCA, Persistent, Trie, XOR or Mo's ( TLE ) )

Dexter's Random Generator | Trie (Keyword Tree) & Data Structures Practice Problems | HackerEarth題意: 給一棵節點帶權的樹。每次詢問一條路徑,問路徑其中一個端點和路徑中任意節點的最大 XOR 值是多少。制約: 1 ≤ N, Q ≤ 1e5 1 ≤ A[ i ] ≤ 1e9解法…

JOI 11 本選 Festivals in JOI Kingdom ( MSSP Dijkstra + Kruskal + Doubling LCA )

Festivals in JOI Kingdom | Aizu Online Judge 先に全ての町について、一番近い祭りの距離を計算する。そして、最大全域木をその最短距離に基づき作る( 祭りに近い方からと遠い方から来ても、近い方を取る )とクエリ( u, v )に対しての答えは ( u, lca( u, …

ABC 14 D - 閉路 ( Doubling LCA )

D: 閉路 - AtCoder Beginner Contest 014 | AtCoder A small practice for doubling LCA. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXQ = 1e5 + 5; const int LGN = 20; // 2 ^ 19 > 1e5 int n; vector<int> G[ MAXN ]; // connects</int></bits/stdc++.h>…

Lowest common ancestor

I have finally started to understand the LCA algorithm for transforming to RMQ. Here are the basic steps for static LCA queries: 1. DFS from any node as the root for the tree, making timestamps as it goes ( called the Euler's tour ). 3 bas…