0w1

Tree

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解法…

CFR 767 C. Garland ( Tree DP )

Problem - C - Codeforces題意: 給一棵節點帶權的樹。問是否存在一種分割方法,使得可以分成三個非空子樹,使得權重總和相同。輸出方案。資料規模: The first line contains single integer n (3 ≤ n ≤ 1e6) — the number of lamps in the garland. Then n…

CFR 792 D. Paths in a Complete Binary Tree ( Ad hoc, Binary Search )

Problem - D - Codeforces題意: 給一個完滿二元樹,用最大編號描述。二元樹上的編號是遞迴配置的,如圖: 給 Q 筆詢問,每筆詢問給起點編號,以及操作字串,字串由 { 'U', 'L', 'R' } 組成,對於不可執行的操作無視之。問終點編號為何。資料規模: The firs…

CFR 781 C. Underground Lab ( Ad hoc, Time Stamp, DFS )

Problem - C - Codeforces題意: 給一個圖,要求放 K 個機器人並給出每個機器人的路徑,路徑長至多為 ceil( 2 * N / K ),使得所有節點都被至少一個機器人拜訪過。資料規模: N, M ≤ 2e5解法: 首先把圖轉換成任意一個生成樹。接著進行類似時間戳記的 DFS,…

POI 2 Stage 3 Step Traversing a Tree ( DFS )

http://main.edu.pl/en/archive/oi/2/obc題意: 給一棵樹,求一個序列,可以不重複拜訪所有節點,而且相鄰節點距離不超過 3。資料規模: In the first line of the standard input there is a positive integer n, not greater than 5000 - it is the number…

POI 2 Stage 2 Mudstock Bis ( Tree, DP )

http://main.edu.pl/en/archive/oi/2/mud題意: 首都在 ( 0, 0 ) 的位置,有 M 個人在首都裡。接著有 L 條線,每條線有若干個城市,依序用線上和前一個 ( 第一個城市和首都 ) 的距離以及人數描述。要求選一個點使得所有人到該點的總花費最小,一個人行走一單…

POI 2 Stage 1 Trees ( DFS )

http://main.edu.pl/en/archive/oi/2/drz題意: 這裡限制樹的每個節點的兒節點必須是 0 或者 2,否則不稱做樹。 給編號由小到大的葉節點的深度,求樹是否存在,存在的話輸出每個節點的父節點編號,以及樹的括號序列表示。資料規模: In the first line of th…

CFR 790 B. Bear and Tree Jumps ( Centroid Decomposition, Divide and Conquer )

Problem - B - Codeforces題意: 給一棵邊權為 1 的樹,問所有有序點對的距離總和。資料規模: N ≤ 2e5 K ≤ 5 TL : 2000 ms解法: 考慮樹分治,分治後都是一個子問題。分別結算子樹本身的貢獻後,計算每個需要經過當前這個重心的點對的貢獻,以及以當前這個…

IOICJ 108 Where is He! ( Tree, Timestamp )

Problem Description: You are given a tree with N nodes. There are Q queries, with u, v, w, where you want to know the node x such that x is a node in the simple path between u and v, where it is also the nearest to w.Constraints: 1≤T≤50 2≤…

IOICJ 92 Double path tree ( Ad hoc, Timestamp )

Problem Description: Given a tree, you want to do the least amount of operations to assert that for any two distinct nodes, there are at least two distinct simple paths that connect them.Constraints: 1≤T≤300 3≤n≤1e5 1≤xi,yi≤n A valid tree …

CFR 533 B. Work Group ( DP )

Problem - B - Codeforces題意: 給一棵以 1 為根的樹,以及點的權重。求一個集合,使得集合內每個點,以自身為子樹的根時,子樹內所有自身以外的點在集合中出現偶數次。問最大可能權重總和。資料規模: The first line contains integer n (1 ≤ n ≤ 2e5) — …

CFR 486 D. Valid Sets ( DP, Tree )

Problem - D - Codeforces題意: 有一棵 n 個節點的樹,各自有一個值 a[ i ]。給你一個 d,求有多少邊和點構成的連通塊集合,滿足最大值和最小值的差不超過 d,模上 1e9 + 7。資料規模: 0 ≤ d ≤ 2000 1 ≤ n ≤ 2000 1 ≤ ai ≤ 2000 TL: 1000 ms ML: 256 MB解…

CFR 14 D. Two Paths ( Ad hoc, Tree, DP )

Problem - 14D - Codeforces題意: 給一棵樹,求兩個不相交的路徑,長度乘積最長可以是多少。資料規模: 節點數: 2 ≤ N ≤ 200 時間限制:1000 ms 空間限制:64 MB解法: 因為樹原本是連通的,而不能相交其實就是有一條路徑可以把他們連起來卻不准連起來,所…

CFR 274 B. Zero Tree ( Tree DP )

Problem - B - Codeforces題意: 有一棵樹,每個節點都有一個值。每次操作可以選一個含節點 1 的樹 ( 邊和節點連通的集合 ),將所有值加一或減一。求至少要多少次操作才能將所有值歸零。資料規模: 節點數: 1 ≤ N ≤ 1e5 值域:abs( V[ i ] ) ≤ 1e9 時間限制…

CFR 734 E. Anton and Tree ( Ad hoc, Tree )

Problem - E - Codeforces題意: 給一棵樹,每個節點有顏色,黑或白。每次可以選一個同顏色的連通分量,將全部顏色反轉。求最少反轉次數,使得樹的所有節點同色。資料規模: 節點數 1 ≤ N ≤ 2e5解法: 先對原圖做連通分量縮點去想。如果用連通分量個數變化的…

CFR 337 D. Book of Evil ( Tree DP )

Problem - 337D - Codeforces題意: 給一棵樹,和若干個指定節點,和 D。求有多少節點,滿足至最遠的指定節點的距離不大於 D。數據範圍: 指定節點數 M,樹大小 N,1 ≤ M ≤ N ≤ 1e5 0 ≤ D 解法: 以 0 為有根樹進行 DP dpd[ i ] : i 號節點與向下最遠的指定…

CFR 120 F. Spiders ( Tree Diameter )

Problem - 120F - Codeforces題意: 給若干顆樹,現在連最少的邊使之連通,求連通後最大直徑。數據範圍: 樹數量 1 ≤ N ≤ 100 樹大小 2 ≤ s[ i ] ≤ 100解法: 求直徑總和即可。直徑的找法是,先對一任意一個點,找到其最遠點。該點至它的最遠點的距離即是直…

CFR 461 B. Appleman and Tree ( Tree DP )

Problem - 461B - Codeforces題意: 給一顆樹,和每個節點是黑是白。求樹的分割組合數,滿足分割後的所有組合都恰有一個黒点,求其余数。數據範圍: 節點數 2 ≤ N ≤ 1e5解法: 樹形動態規劃寫起來真蛋疼。。。 將 0 作為根,轉換為有根樹上的問題。 dp[ i ][…

CFR 161 D. Distance in Tree ( Tree DP )

Problem - 161D - Codeforces題意: 給一棵樹,求滿足距離為 K 的點對數。 解法:O( N * K ) cdis[ u ][ i ] : count of nodes v, such that v is part of the subtree of u, and is exactly i edges aways from u cdis[ u ][ i ] = SIGMA{ cdis[ v ][ i - 1…