T1 太简单了，T6 太赛博了，那就写一下 T2,3,4,5 吧。
题解风格仍然意识流。
*loj3980. 「NOI2023」桂花树
tag：DP，计数。
送我出队的题。
先考虑 \(k=0\) 的情况。使用类似树背包的方法是可以做的，但是单次插入一棵子树过于笨重，所以只能考虑单次插一个点。然后发现每次只可能插叶子或者插边上，直接双阶乘就好了。
考虑 \(k>0\) 的情况，每次维护前缀的虚树。那么可以发现虚树上一些未确定标号的点必然在后面 \(k\) 个点里面，所以记录状态表示 \(i\) 的父亲是否是一个虚点，每次可能插边上，可能插点上，也可能把一个虚点插边上然后挂到虚点上面，也可以夺舍一个虚点。
然后就 \(\mathcal{O}(Tmk2^k)\)，就过了。
*loj3981. 「NOI2023」深搜
tag：DP，数据结构，容斥，计数。
考场上钻牛角尖了，来想一想。
好像会了 B 性质。B 性质的意思是只有返祖边，那么考虑钦定一些合法的点然后容斥。注意到条件就是：关键点到达所有路径的第一个点一定是端点。考虑决策方式，也就是能够确定每次传一个关键点上来的时候保证没有一条路径跨过这个点即可。在顶上决策不太行，但是发现从底下开始决策就只要记录 \(\mathcal{O}(n)\) 的 mask，那就很好啊。线段树合并可以做到 \(\mathcal{O}(n\log n)\)。
好像也可以做到 \(\mathcal{O}(n^3)\)，大概就是枚举其中一个合法的关键点，然后钦定它是编号最小的就好了，同样可以做到 \(\mathcal{O}(n^2\log n)\)。
但是这样就不太行。考虑另外一种判断合法的方式：建立钦定关键点的虚树（注意此处的虚树满足每个点度数至少为 \(3\)，就是如果根只有两个儿子，我们直接在两个儿子直接连边），那么路径一定在虚树上相邻两个结点之间，或者是虚树外的一条祖先链。
在此基础上考虑 B 怎么做。每次转移是枚举子树中的一个点，然后加入虚树上这两条边之间的边的决策。我们不妨在往上做的过程中动态维护这个东西，讨论一下就可以发现实际上转移为子树乘 \(2\)，只需要把树拍到 dfs 序上面就好了。所以可以线段树做到 \(\mathcal{O}(n\log n)\)。
考虑有横叉边的情况。发现唯一的问题在于我们刚才强调的，根只有两个儿子的情况，横叉边可以插入在里面，成为虚树上被一条边完全包含的边。枚举 LCA \(l\) 和两个儿子 \(u,v\)，那么贡献是被 \(u,v\) 包含的路径，那么再把树拍扁到 dfs 序上面，问题变成矩形乘和全局求和。这个单独对每个 \(l\) 做扫描线即可。
于是总复杂度 \(\mathcal{O}(n\log n)\)。
loj3982. 「NOI2023」贸易
观察到路径一定是：\(u\) 跳到 LCA，然后往上一段，往下一条边，往上一段，往下一条边……如此直到跳到 \(v\) 的子树。
所以可以考虑在 LCA 处统计贡献。前提是我们需要处理反图上 \(v\) 到它祖先任意点的距离，这个因为路径形态比较好所以可以直接 DP。所以复杂度 \(\mathcal{O}(2^nn^2)\)。
其实把 \(u\) 的祖先和子树拉出来一起跑 Dijkstra 也是对的，用到的是子树和和深度和的结论，感觉我总是忘记子树和。
*loj3983. 「NOI2023」字符串
tag：字符串。
我感觉单 \(\log\) 很难的啊。
思考一下 NOI 有什么字符串考点，发现有 SA，所以考虑 SA。那么把它后缀排序之后可以得到一个简单做法：判断反串 SA 在区间有多少个位置的 \(rk\) 大于 \(rk_i\)。
但是你发现这样非常不好，因为回文串会重复算。考虑容斥掉回文串。那么问题是要算 \([i,i+2r-1]\) 有多少个回文前缀满足 \(rk_j>rk_i\)。
这个东西肯定是不能直接做的，所以要转化一下条件。\(rk_i>rk_j\) 且条件是回文串，因为是回文串所以这两个东西同时删掉一个前缀也不影响，于是两个串变成了开头结尾相接在回文中心的两个串，所以大小关系就只和回文中心有关了。于是你可以考虑在回文中心统计答案。
这样做的好处就是确定了回文中心之后，回文串的信息是相对连续的，因为只要沿回文中心向两边延伸即可。稍微转化一下你发现这东西变成二维数点了。
考虑 border 理论相关内容可以得到其它做法。最近杭电有个 Z 函数题和这东西某种意义上有点像，那个题的一种枚举方法需要找 border，另一种枚举方法只需要找一个前缀和后缀，问题的难度也是不同的。此题的回文串也是如此。