SDOI/SXOI2022做题笔记持续更新中……题目：https://www.luogu.com.cn/problem/list?tag=114%7C59&page=1目录SDOI/SXOI2022做题笔记[SDOI/SXOI2022]小N的独立集[SDOI/SXOI2022]整数序列[SDOI/SXOI2022]小N的独立集时间复杂度\(O(n^2k^4)\)。ケロシの代码constin

存下每个点的父亲信息\(fa\)和点权\(w\)就已经用去近\(54\text{MiB}\)了，树剖似得彻彻底底。考虑树分块：随机选定\(\sqrtn\)个点作为关键点建虚树，这样每个点向上走到关键点的步数期望为\(\sqrtn\)，然后每个关键点存原树上从它到它虚树上的父亲结点的信息。dfs似了，

还是先打暴力，枚举\(k^n\)种树的形态做树形DP，时间复杂度\(\mathcalO(nk^n)\)，拿下\(n\le8\)和\(k=1\)的\(25\)分。虽然很简单，还是交代下吧：设\(f(u,0/1)\)表示以\(u\)为根的子树中是否选\(u\)的最大权独立集，\(f(u,0)\getsw_u+\sum\limits_{v\inson_u}

记\(len_x\)为\(x\)在\(a\)中出现的次数，显然有\(\mathcalO(nq)\)的暴力，拿下\(20\)分。感觉用数据结构难以维护，考虑根号做法。根号做法有一个阈值\(L\)，然后分讨（钦定\(len_x\lelen_y\)）：\(len_x\lelen_y\leL\)直接暴力做，时间复杂度\(\mathcalO(L)\)。\(L