Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"洛谷-P2048\":[\"超级钢琴\",7409,\"NOI2010\"],\"洛谷-P2146\":[\"软件包管理器\",10460,\"NOI2015\"],\"洛谷-P2542\":[\"航线规划\",2451,\"AHOI2005\"],\"洛谷-P5536\":[\"核心城市\",4529,\"XR-3\"],\"洛谷-P3313\":[\"旅行\",4460,\"SDOI2014\"],\"洛谷-P3379\":[\"最近公共祖先(LCA)\",124438,\"模板\"],\"洛谷-P6722\":[\"Village 村庄\",492,\"MCOI-01\"],\"洛谷-P1117\":[\"优秀的拆分\",7129,\"NOI2016\"],\"洛谷-P4408\":[\"逃学的小孩\",4775,\"NOI2003\"],\"AtCoder-abc291_h\":[\"Balanced Tree\",315,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/abc291\\\"\\u003eAtCoder Beginner Contest 291(Sponsored by TOYOTA SYSTEMS)\\u003c/a\\u003e\"],\"CodeForces-1401D\":[\"Maximum Distributed Tree\",9035,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1401\\\"\\u003eCodeforces Round 665 (Div. 2)\\u003c/a\\u003e\"],\"CodeForces-1467E\":[\"Distinctive Roots in a Tree\",1365,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1467\\\"\\u003eCodeforces Round 695 (Div. 2)\\u003c/a\\u003e\"],\"Gym-104400K\":[\"The Demon Jester\",11,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104400\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eHunan University 2023 the 19th Programming Contest\\u003c/a\\u003e\"],\"洛谷-P2590\":[\"树的统计\",15254,\"ZJOI2008\"],\"洛谷-P3384\":[\"重链剖分/树链剖分\",42706,\"模板\"],\"洛谷-P5022\":[\"旅行\",13736,\"NOIP2018 提高组\"],\"LibreOJ-10135\":[\"祖孙询问\",1907,\"一本通 4.4 练习 2\"],\"洛谷-P5021\":[\"赛道修建\",9464,\"NOIP2018 提高组\"],\"洛谷-P1084\":[\"疫情控制\",11224,\"NOIP2012 提高组\"],\"洛谷-P5049\":[\"旅行 加强版\",2592,\"NOIP2018 提高组\"],\"洛谷-P1364\":[\"医院设置\",28301,null],\"洛谷-P3304\":[\"直径\",2801,\"SDOI2013\"],\"洛谷-P3865\":[\"ST 表\",74646,\"模板\"],\"洛谷-P8818\":[\"策略游戏\",7143,\"CSP-S 2022\"],\"洛谷-P3703\":[\"树点涂色\",2299,\"SDOI2017\"],\"POJ-1655\":[\"Balancing Act\",7513,\"\\u003cdiv class\\u003d\\\"ptx\\\" lang\\u003d\\\"en-US\\\"\\u003e\\u003ca href\\u003d\\\"http://poj.org/searchproblem?field\\u003dsource\\u0026amp;key\\u003dPOJ+Monthly--2004.05.15+IOI+2003+sample+task\\\"\\u003ePOJ Monthly--2004.05.15 IOI 2003 sample task\\u003c/a\\u003e\\u003c/div\\u003e\"],\"洛谷-P1600\":[\"天天爱跑步\",10945,\"NOIP2016 提高组\"],\"CodeForces-1406C\":[\"Link Cut Centroids\",10128,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1406\\\"\\u003eCodeforces Round 670 (Div. 2)\\u003c/a\\u003e\"],\"洛谷-P1967\":[\"货车运输\",29583,\"NOIP2013 提高组\"],\"洛谷-P5829\":[\"失配树\",2824,\"模板\"],\"洛谷-P3629\":[\"巡逻\",5225,\"APIO2010\"],\"CodeForces-519E\":[\"A and B and Lecture Rooms\",7103,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/519\\\"\\u003eCodeforces Round 294 (Div. 2)\\u003c/a\\u003e\"],\"HDU-7332\":[\"Tree\",225,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2023%A1%B0%B6%A4%B0%D2%B1%E0%B3%CC%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A85%A3%A9\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2023“钉耙编程”中国大学生算法设计超级联赛(5) \\u003c/a\\u003e \\u003c/div\\u003e\"],\"洛谷-P3292\":[\"幸运数字\",3861,\"SCOI2016\"],\"洛谷-P4381\":[\"Island\",3983,\"IOI2008\"],\"Gym-104354B\":[\"Art for Rest\",354,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104354\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2023 CCPC Henan Provincial Collegiate Programming Contest\\u003c/a\\u003e\"],\"洛谷-P2680\":[\"运输计划\",16377,\"NOIP2015 提高组\"],\"洛谷-P2880\":[\"Balanced Lineup G\",23336,\"USACO07JAN\"],\"洛谷-P1351\":[\"联合权值\",18661,\"NOIP2014 提高组\"],\"Gym-104354F\":[\"Art for Last\",678,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104354\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2023 CCPC Henan Provincial Collegiate Programming Contest\\u003c/a\\u003e\"],\"CodeForces-161D\":[\"Distance in Tree\",14977,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/161\\\"\\u003eVK Cup 2012 Round 1\\u003c/a\\u003e\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"Cowbby","updateTime":1693209509000,"title":"(Section 8) ST表、树的基础、LCA、树链剖分","dislikeCnt":0,"content":"#### 飞书上的讲解文档\nhttps://fudanicpc.feishu.cn/wiki/SamAwZZzriO9QNkWvqJcYUnynMb\n\n各表中题目总体符合难度梯度\n#### 一、ST 表\n[problem:洛谷-P2880]\n[problem:洛谷-P3865]\n[problem:Gym-104354B]23春季随机组队赛\n[problem:Gym-104354F]23春季随机组队赛\n[problem:洛谷-P2048]\n[problem:洛谷-P8818]\n[problem:洛谷-P1117]*后缀数组 height 数组上 RMQ。本题新增。——lhc 0526\n#### 二、树的基础\n##### CF div2. 中间题级别及以下的树上综合性问题\n[problem:洛谷-P1364]\n[problem:洛谷-P1351]\n[problem:HDU-7332]“伪树链剖分”;本题新增——lhc 08288\n[problem:CodeForces-161D]\n[problem:CodeForces-1401D]\n##### 树的直径及其性质\n[problem:洛谷-P4408]几乎是模板。本题之前放错了,已更新。——lhc 0526\n[problem:洛谷-P3304]\n[problem:洛谷-P5536]\n[problem:洛谷-P6722]\n[problem:洛谷-P4381]可能稍难\n[problem:洛谷-P3629]可能稍难\n##### 树的重心及其性质\n[problem:POJ-1655] 模板\n[problem:CodeForces-1406C]\n[problem:AtCoder-abc291_h]23春季个人赛;推荐一写\n##### 一些有一定难度树上综合性问题\n适合锻炼思维,提升能力(做过也可以重新想一下啦,不要狂刷 AC 率ww)\n[problem:洛谷-P5022]基环树\n[problem:Gym-104400K](0705新增)树上倍增和简单dp;23春季期末后随机组队赛\n[problem:洛谷-P5049]基环树\n[problem:洛谷-P5021]\n[problem:CodeForces-1467E]\n[problem:洛谷-P1084]\n[problem:洛谷-P1600]\n#### 三、LCA\n[problem:洛谷-P3379]模板,要求用倍增法实现\n[problem:LibreOJ-10135]\n[problem:洛谷-P5829](0705新增)Section 2 中 KMP 题单第2题\n[problem:CodeForces-519E]\n[problem:洛谷-P1967]最小(大)生成树\n6 闇の連鎖 https://www.acwing.com/problem/content/354/\n7 异象石 https://www.acwing.com/problem/content/357/\n8 [problem:洛谷-P3292]线性基\n#### 四、树链剖分\n[problem:洛谷-P3379]要求用树链剖分法实现,并将其用时与倍增法进行比较\n[problem:洛谷-P3384]模板\n[problem:洛谷-P2590]\n[problem:洛谷-P2146]\n[problem:洛谷-P2680]\n[problem:洛谷-P3313]\n[problem:洛谷-P2542]\n[problem:洛谷-P3703]","threadId":144478,"likeCnt":0,"createTime":1684345834000,"isWorkbook":true,"viewCnt":1128,"openness":2,"fav":false,"id":3668,"trustable":false}