Hooch

考场上写出： 1if (sub1 :: check()) sub2 :: solve(); 这个sb操作直接少 60pts。 T1. 脐 题意 给定一个长度为 nnn 的排列 ppp，求有多少棵树满足： ∀1≤i<j≤n\forall 1 \le i < j \le n∀1≤i<j≤n，如果树中存在边 (i,j)(i, j)(i,j)，那么一定存在边 (pi,pj)(p_i, p_j)(pi​,pj​)。 答案对 998244353998244353998244353 取模。 1≤n≤2×1061 \le n \le 2 \times 10^61≤n≤2×106。 题解 不会。 T2. 最初日 题意 给定一个 n×nn \times nn×n 的矩阵 aaa，每行每列都是 1∼n1 \sim n1∼n 的排列。 你要选出 nnn 个格子，满足每行每列都只有一个格子被选中。设 rir_iri​ 是第 iii 行被选中的格子的元素，cic_ici​ 是 iii 列被选中的格子的元素。要求你选的格子满足，∀1≤i,j≤n\forall 1 \le i, j \le n∀1≤ ...

网络最大流 原版 板子没什么好说的，代码： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657struct flow { int head[N], nex[M << 1], tot = 1, dep[N], S, T, cur[N]; bool vis[N]; struct E { int to, nxt, flow; } edge[M << 1]; void ad(int x, int y, int z) { edge[++tot] = (E) {x, y, z}; nex[tot] = head[x]; head[x] = tot; } void add(int x, int y, int z) { ad(x, y, z); ad(y, x, 0); } bool ...

前置知识点：虚树，dp。 题意 给定一个 nnn 个点 mmm 条边的无向简单联通图，满足 n−1≤m≤n+10n - 1 \le m \le n + 10n−1≤m≤n+10。求图的独立集个数，对 998244353998244353998244353 取模。 题解 首先，注意到 m≤n+10m \le n + 10m≤n+10，也就是说非树边只有最多 111111 条。将这些非树边连接的 s=22s=22s=22 个点（下面称为关键点）找出来，接着 2s2^s2s 枚举每个关键点的状态，最后对整棵树树形 dp 就可以在 O(n2s)\mathcal{O}(n2^s)O(n2s) 复杂度下解决这个问题，可以得到 70+pts 的好成绩。 于是沿着这一条思路，可以想办法优化。我们先将朴素树形 dp 给推出，设 fx,0/1f_{x, 0 / 1}fx,0/1​ 表示 xxx 为根的子树中 xxx 选或不选的方案数。那么有： {fx,0=∏v∈x.son(fv,0+fv,1)fx,1=∏v∈x.sonfv,0\begin{cases} f_{x, 0} = \prod\limits_{v ...

高斯消元 高斯消元是用于求解 nnn 元线性方程组的算法。这里不讲别的，只讲算法流程。 首先，可以用一个 nnn 行 (n+1)(n + 1)(n+1) 列的矩阵来表示一个 nnn 元线性方程组： {a1,1x1+a1,2x2+⋯+a1,nxn=a1,n+1a2,1x1+a2,2x2+⋯+a2,nxn=a2,n+1⋯an,1x1+an,2x2+⋯+an,nxn=an,n+1\begin{cases} a_{1, 1}x_1 + a_{1, 2}x_2 + \cdots + a_{1, n} x_n = a_{1, n + 1}\\ a_{2, 1}x_1 + a_{2, 2}x_2 + \cdots + a_{2, n} x_n = a_{2, n + 1}\\ \cdots\\ a_{n, 1}x_1 + a_{n, 2}x_2 + \cdots + a_{n, n} x_n = a_{n, n + 1} \end{cases} ⎩⎨⎧​a1,1​x1​+a1,2​x2​+⋯+a1,n​xn​=a1,n+1​a2,1​x1​+a2,2​x2​+⋯+a2,n​xn​=a2,n+1​⋯a ...

前置知识：线段树合并，可持久化线段树，边分治，可能会用到一点点虚树。 P4565 边分树神题啊。。。 题意 给定两棵边有边权的树 T1,T2T_1, T_2T1​,T2​，结点数都为 nnn。设 di(x)d_i(x)di​(x) 表示第 iii 棵树上 xxx 的带权深度， 求一组点对 (x,y)(x, y)(x,y)，使得 d1(x)+d1(y)−d1(p)−d2(p′)d_1(x) + d_1(y) - d_1(p) - d_2(p')d1​(x)+d1​(y)−d1​(p)−d2​(p′) 最大， 其中 p,p′p, p'p,p′ 分别代表 x,yx, yx,y 在两树上的 LCALCALCA。为了方便，只需输出最大值。 题解 先考虑变换一下这个式子，设 disi(x,y)dis_i(x, y)disi​(x,y) 表示 (x,y)(x, y)(x,y) 在第 iii 棵树上的距离。那么原式就等于 12(dis1(x,y)+d1(x)+d1(y)−2d2(p′)){1 \over 2}(dis_1(x, y) + d_1(x) + d_1(y) - 2d_2 ...

边分治神题。 前置知识：边分治，虚树。 题意 给定 333 棵有边权的树，每棵树都含有 nnn 个节点，令 disi(x,y)dis_i(x, y)disi​(x,y) 表示 (x,y)(x, y)(x,y) 在第 iii 棵树上的距离。求一组 (i,j)(i, j)(i,j)，使得 ∑k=13disk(i,j)\sum\limits_{k = 1}^3 dis_k(i, j)k=1∑3​disk​(i,j) 最大，为了方便，只需输出最大值。 题解 考虑边分治。下面用 TiT_iTi​ 来表示第 iii 棵树。 对 T1T_1T1​ 进行边分治，设 d1(x)d_1(x)d1​(x) 表示 xxx 点到分治边一侧的距离，那么答案就转化成了 d1(i)+d1(j)+dis2(i,j)+dis3(i,j)d_1(i) + d_1(j) + dis_2(i, j) + dis_3(i, j)d1​(i)+d1​(j)+dis2​(i,j)+dis3​(i,j)。然后将当前分治块内的所有点在 T2T_2T2​ 上拉出来，建一棵虚树 T2′T'_2T2′​，再设 d2(x)d_2(x ...

动态 DP P4719 动态 DP: 题意 给定一棵 nnn (n⩽105n \leqslant 10^5n⩽105) 个点的树，点带点权。 有 mmm (m⩽105m \leqslant 10^5m⩽105) 次操作，每次操作给定 x,yx,yx,y，表示修改点 xxx 的权值为 yyy。 你需要在每次操作之后求出这棵树的最大权独立集的权值大小。 题解 首先考虑 m=0m=0m=0 时的做法，可以简单地设计出 dp 转移方程式 fx,0/1f_{x, 0 / 1}fx,0/1​ 表示 xxx 选或不选的答案。 {fx,0=∑v∈x.sonmax⁡{fv,1,fv,0}fx,1=px+∑v∈x.sonfv,0\begin{cases} f_{x, 0} = \sum\limits_{v \in x.\text{son}} \max\{f_{v, 1}, f_{v, 0}\} \\ f_{x, 1} = p_x + \sum\limits_{v \in x.\text{son}} f_{v, 0} \end{cases} ⎩⎨⎧​fx,0​=v∈x.son∑​max{fv,1​,fv,0 ...

神题啊！神题（赞叹） 形式化题意 给定一棵 nnn 个点的树，第 iii 个点有点权 aia_iai​。且每个点都有颜色，初始时颜色都为 111，第 iii 个点的颜色是 cic_ici​。 你可以对一个点 xxx 进行一次操作： 计数有多少 vvv，满足 vvv 在 x→1x \to 1x→1 的路径（包含 xxx 和 111）上，且 cv≠xc_v \ne xcv​=x。 将满足条件的 vvv 的个数记作 cntcntcnt，并使 ans:=ans+cntans := ans + cntans:=ans+cnt，初始时 ans=0ans = 0ans=0。 将 x→1x \to 1x→1 路径上的点颜色全部变为 xxx。 现在知道了第 iii 个点总共被操作 aia_iai​ 次，问如何安排 ∑a\sum a∑a 次操作，使最后 ansansans 最大。然后还有 mmm 个询问，每次如下： x w 表示将 ax:=ax+wa_x := a_x + wax​:=ax​+w 后的答案。 题解 第一步就是一个比较难的性质的观察：每个点对答案的贡献是相互独立的。这里每个点对答案 ...

又是一道妙题，加深了蒟蒻对 LCT\text{LCT}LCT 的理解。 题意 给定一棵 nnn 个节点的有根树，根节点为 111。最开始每个节点都有颜色，且颜色互不相同。 定义一条路径的权值为：路径上点的不同颜色数。 现在一共会有 mmm 组询问，每组询问有三种： 1 x 将 xxx 到根节点 111 上的所有点都染色为以前从未出现过的颜色。 2 x y 询问 x→yx \to yx→y 路径的权值。 3 x 询问 xxx 的子树内的结点中，到根节点的路径的最大权值。 题解 思路 考虑如何维护 111 操作，容易想到：任一时刻，对于每种颜色，拥有该颜色的点在树上的联通块有且仅有一个，且一定是直上直下的链。 这个性质的存在，使得此题可以用 LCT\text{LCT}LCT 解决。一个经典的处理方法是： 对于 LCT\text{LCT}LCT 上的一条边，若两端点的颜色相同，则该边为实边。 若两端点颜色不同，该边为虚边。 容易证明这种赋实边、虚边的方法是符合 LCT\text{LCT}LCT 的性质的。 所以操作 111 就可以转换成 LCT\text{LCT}LCT 的 acce ...

神题，神题啊！！（战术后仰） 题意 给定一棵 nnn 个节点的树，点有点权。有 mmm 个询问，每次询问规定某两个点选或不选，求最小点覆盖。 题解 概念 做题的第一步是：看懂题意。 点覆盖：在树上选择某些点，使得对于树上的每一条边，都满足两端点至少有一点被选。 最小点覆盖：即选择的点点权和最小的点覆盖。 独立集：在树上选择某些点，使得对于树上的每一条边，都满足两端点没有同时被选。 最大独立集：即选择的点点权最大的独立集。 不难看出，**一棵树上的点覆盖和独立集是一一对应的，一个点覆盖的补集就是一个独立集。**所以，最大独立集是最小点覆盖的补集。（虽然这些东西和题意无关，但还是可以扯一下） 思路 先考虑没有询问时，如何求得最小点覆盖？答案是显然的，直接树形 dp 即可，设 fx,0/1f_{x, 0 / 1}fx,0/1​ 表示 xxx 为根的子树中，xxx 选或不选的最小点覆盖权值和，则有： fx,0=∑v∈x.sonfv,1fx,1=∑v∈x.sonmin⁡{fv,0,fv,1}+px\begin{aligned} f_{x, 0} &= \sum\li ...