目录
目录
缺失题目：R15T3 .
R15T1 树 V 图
原题：SNOI2024 D1T1 .
注意到答案肯定是形如每个连通块选一个点组成，把连通块缩起来后令 \(dp_{u,x}\) 表示连通块 \(u\) 选 \(x\) 的方案数，每次合并子树转移即可 .
因为只有 \(n^2\) 个合法点对所以时间复杂度为 \(O(n^2)\) . 判无解比较麻烦 .
R15T2 矩阵
原题：SNOI2024 D1T2 .
维护十字链表，每次转的时候直接改指针（这里指针方向可以直接钦定一个相对顺序，在矩形外面加个框就可以走的时候转为绝对顺序）.
矩形加的时候差分即可，每次转的时候需要暴力重构边上的差分值 .
时间复杂度 \(O(n(n+q))\)，不太想写 .
标签：连通,原题,省选,题解,复杂度,R15T2,2024,R15T1 From： https://www.cnblogs.com/CDOI-24374/p/17979250