Codeforces树形结构题单

【CF 1200-1600 - 树形结构】(基础遍历, 简单LCA思想)

• CF115A Party (DFS/BFS求森林中树的最大深度)
• CF580C Kefa and Park (树上DFS/BFS，路径限制)
• CF1006E Military Problem (DFS序 + 二分查找子树第k个)
• CF1325C Ehab and Path-etic MEXs (树的构造，利用叶子节点性质分配边权)
• CF1249B2 Books Exchange (hard version) (置换环分解，求环长，类似功能图)
• CF474D Flowers (DP，但状态转移可以看作树形依赖)
• CF1020B Badge (DFS/模拟，每个点出发必然进入一个环，功能图)
• CF1389A LCM Problem (构造，与树关系弱)
• CF1294F Three Paths on a Tree (求树的直径及相关端点，构造三条路径覆盖最多点)
• CF734B Anton and Digits (贪心构造数字)
• CF1334B Middle Class (排序贪心)
• CF276D Little Girl and Maximum XOR (按位贪心构造最大异或)
• CF1373C Pluses and Minuses (前缀和模拟)
• CF339D Xenia and Bit Operations (线段树，但操作在完全二叉树结构上)
• CF1363A Odd Selection (组合计数/贪心)
• CF766B Mahmoud and a Triangle (排序贪心判断三角形)
• CF1093B Letters Rearranging (判断回文或构造非回文)
• CF1303B National Project (贪心计算天数)
• CF1144C Two Shuffled Sequences (构造两个单调序列)
• CF1358B Maria Breaks the Purity (贪心)
• CF1201A Important Exam (按位贪心)
• CF431C k-Tree (DP，k叉树计数)
• CF1005C Summarize to the Power of Two (map/hash暴力检查)
• CF706C Hard problem (DP，字符串字典序，相邻关系构成链)
• CF977F Consecutive Subsequence (DP求LIS变形，map记录前驱)
• CF1207A There Are Two Types Of Burgers (贪心)
• CF1380A Three Indices (找局部峰/谷)
• CF1350A Orac and Factors (模拟迭代找最小质因子)
• CF1328C Ternary XOR (贪心构造)
• CF1324D Pair of Topics (排序+双指针/二分)

【CF 1600-2100 - 树形结构】(LCA, 树形DP, DSU on Tree, 树上差分)

• CF191C Fools and Roads (LCA + 树上差分统计边经过次数)
• CF337D Book of Evil (树形DP/两次DFS求树上最远点对中点相关的统计)
• CF600E Lomsat gelral (DSU on Tree / 树上启发式合并) (统计子树颜色众数)
• CF461B Appleman and Tree (树形DP，统计黑色节点连通块方案)
• CF1027D Mouse Hunt (基环树森林，找每个基环树上权值最小的环)
• CF1076D Edge Deletion (Dijkstra树/BFS树，从根出发保留k条最短路径树的边)
• CF1213G Path Queries (Kruskal重构树思想 / 并查集按边权从小到大加边离线处理路径上点对数)
• CF839C Journey (树上期望DP / DFS计算路径期望长度)
• CF1305D Kuroni and the Celebration (交互题，通过查询两点LCA逐步缩小范围找根)
• CF1328E Tree Queries (LCA判断路径包含/祖先关系)
• CF1009D Compatible Numbers (构造图，虽然不一定是树但常涉及树的性质)
• CF118E Bertown roads (Tarjan找桥，然后在DFS树上给边定向构造强连通（除了桥）)
• CF570D Tree Requests (DFS序 + 离线查询子树内字符能否构成回文 / DSU on Tree)
• CF342E Xenia and Tree (点分治/树上莫队/动态维护重心信息，处理多次查询)
• CF739A Alyona and mex (构造，与树关系弱，但常和树上mex一起出现)
• CF375D Tree and Queries (DSU on Tree，查询子树中出现次数>=k的颜色数)
• CF1093D Beautiful Tree (二分图染色 + DP计数)
• CF486D Valid Sets (树形DP/点分治，统计满足权值限制的连通块)
• CF620E New Year Tree (树链剖分/DFS序+线段树维护颜色集合(状压))
• CF1056E Check Transcription (字符串哈希 + KMP思想/DFS爆搜分配长度)
• CF1101D GCD Counting (树形DP，维护从根到当前节点路径上的GCD信息以及质因子)
• CF741B Arpa's weak point and Mehrdad's valuable common ancestors (并查集缩点 + 背包DP，如果看作森林)
• CF1304E1 Ehab and the Expected GCD Problem (easy) (期望线性性 + LCA)
• CF915E Physical Education Lessons (动态开点线段树/珂朵莉树，区间操作，如果树上...)
• CF1245D Shichikuji and Power Grid (最小生成树，建立超级源点)
• CF1363C Game On Leaves (博弈论，判断谁能取到树的某个关键点)
• CF1033C Permutation Game (记忆化搜索/博弈DP，建图，如果图是树...)
• CF1251D Salary Changing (二分答案 + 贪心，树上问题可类似)
• CF1187C Vasya and Array (差分约束/构造，如果限制在树上...)
• CF1092F Tree Cutting (Hard Version) (换根DP)

【CF 2100-2500+ - 树形结构】(LCT, 点分树, 虚树, 复杂树上数据结构)

• CF487E Tourists (圆方树 / 点双连通分量 + 树链剖分/LCT维护路径最小值)
• CF603E Pastoral Oddities (LCT维护动态最小生成森林 / 整体二分 + 可撤销并查集)
• CF343D Water Tree (树链剖分/LCT，维护子树覆盖和路径查询)
• CF1083E The Fair Share (斜率优化DP + 李超线段树/凸包，如果DP在树上...)
• CF671D Roads in Yusland (树形DP + 李超线段树合并 / 全局平衡二叉树)
• CF915F Stas and the Queue at the Buffet (Kruskal重构树 / 启发式合并维护连通块信息并计算贡献)
• CF1039D You Are Given a Tree (长链剖分优化树形DP / 根号分治按k值处理路径划分)
• CF1060E Sergey and Subway (换根DP / 计算每条边对总路径长度(奇偶性)的贡献)
• CF1280C Divide and Conquer (树形DP，计算每条边对两种答案(子树大小奇偶性)的贡献)
• CF1187E Tree Painting (换根DP，计算涂色最大得分)
• CF1009F Dominant Indices (长链剖分优化DP/DSU on tree，求每个子树中深度最大的出现次数最多的深度)
• CF1098C Construct a tree (构造，贪心分配子节点使得子树和的平方和最小)
• CF1100F Ivan and Burgers (线性基求区间异或最大值，如果区间在树上...)
• CF1137C Museums Tour (Tarjan缩点 + DAG上分层图DP/最长路，考虑星期)
• CF555E Case of Computer Network (树上差分 + Tarjan边双缩点，判断边是否必须同向使得两点可达)
• CF1054E Chips Puzzle (构造，虽然是网格图，但树上移动棋子问题类似)
• CF1080F Vova and Train (二分答案 + 主席树/二维数据结构判断区间是否有可用列车，如果区间在树上...)
• CF1290E Cartesian Tree (笛卡尔树 + 数据结构维护区间信息，笛卡尔树本身是树)
• CF1117G Reversing and Concatenating (SAM + 线段树合并/树剖，SAM的parent树)
• CF1017G The Tree (树链剖分 + 线段树维护复杂标记和操作)
• CF1174E Ehab and the Expected GCD Problem (期望DP，质因数分解，如果问题在树上...)
• CF1056E Check Transcription (字符串哈希 + KMP思想/DFS爆搜分配长度，如果01串是树的编码...)
• CF1045A Last Chance (网络流最大权闭合子图，如果依赖关系是树...)
• CF1270G Subset with Max XOR Sum (线性基，图论找环，如果图是基环树...)
• CF1023F Mobile Phone Network (Boruvka算法思想 / Kruskal + LCA判断能否加边形成更优MST)
• CF1142E Pink Floyd (交互题，SCC缩点后在DAG上找特殊点，如果DAG是树的变形...)
• CF914F Substrings in a String (bitset优化字符串匹配，如果文本串是树的序列化...)
• CF1067E Random Forest Rank (高斯消元求矩阵秩，图论与代数结合，如果森林...)
• CF1208G Polygons (KMP求最小循环节 + 欧拉函数计数，如果串是树的编码...)
• CF932G Palindrome Partition (PAM + fail树上DP优化/回文border理论，PAM的fail树)