Problem Description: There are N items, the i'th item costs C[i], and we have a coupon that can reduce its price by D[i]. However, for every coupon i to be effective, coupon X[i] must be used, i.e., i'th item bought. You have B units of mo…

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

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

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

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

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

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

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

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≤…

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 …

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

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

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

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

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

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

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

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

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…