123
G
显然把整棵树分成两部分，然后单向过去这样子是一个乘法，答案肯定最优。那么直接找重心，跑一个背包，注意到最多 \(O(\sqrt n)\) 种不同的子树大小，于是合并的时候用一下2的幂次优化，再套个bitset的复杂度就是 \(O(\frac{n\sqrt{n}}{w})\) 的，可以通过。
1 | bitset<1000000> res; |
或者你也可以考虑多项式乘法，同一种子树大小压到一个式子里，总复杂度是 \(O(n\sqrt{n}\log n)\) 的，看板子速度也可以通过。
N
somehow枚举一下。
考虑 \((x,y,x',y')\) 表示 \(a_{x,y}>\max\{a_{x,y'},a_{x',y}\}\)，这样的四元组有几个。然后考虑到一个不合法的贡献2个这样的四元组，合法的贡献1个，那么就好算了。
C
设\(F_k\)是一个以\(k\)为下标的二元矩阵，矩阵的第\(i\)行\(j\)列表示从\(i\)出发，结束到\(j\)的路径有多少条。假设\(E\)是邻接矩阵，\(D\)是度数矩阵，那么可以写出\(F_k\)的递推式：
\[ F_k=F_{k-1}E-(D-I)F_{k-2} \]
后面的减法是为了减去从\(k-1\)走到\(k\)却回到了\(k-2\)的点，\(D\)还要再减去\(I\)是为了刨除跟\(k-3\)相等的那部分非法情况，防止多减。这个递推整理再成矩阵，搞一个矩阵套矩阵就能\(8n^3\log\)计算。初始\(F_0=I\)，\(F_1=E\)，注意特判\(F_2=F_1E-DF_0\)，这里第0步没有上一步，不需要减去\(I\)。
J
好题
考虑网络流建图
- 源点连向每个 \(1\)，边权 \(\infty\)
- 每个 \(n\) 连向汇点，边权 \(\infty\)
- 同行列的差为 \(1\) 的两个点连边，边权 \(\infty\)
- 每个点拆成入点出点，入点向出点连边，边权 \(1-b_{i,j}\)
我们发现一个合法的方案会把这个图割开，方案的代价就是割边的权值和，那么代价最小的方案就是最小割，同时为了限制只选 \(n\) 个点，可以将入点出点间边权加上 \(n+1\)，最后算答案的时候统一减去即可。
B
不知道怎么想出来的，这个题太考感觉了
假设三个串长度是\(l_1,l_2,l_3\)，考虑建立三分图，每个部分\(l_i\)个点，然后不同部分之间，相同字母连边。假设这个图的最大匹配是\(m\)，取\(m'=\min \{l_1,l_2,l_3,m\}\)，考虑用最大匹配先生成\(m'\)张卡片，然后刨除对应字母。剩下的字母中，三个串字符集要么至少一个为空，要么互相不交。如果一个为空，取剩下两者最大值。如果互相不交，简单匹配一下即可。
K
呵呵这个题疑似有点太水了，没看见血亏一辈子，，，，，，
理性观察发现关于横纵坐标独立是单峰的，先来一个三分套三分，然后问题转化成给定一个点怎么求答案。一个点到三角形三顶点距离之和最短，这是小学奥数交给我们的费马点问题hh，[deleted]回忆一下[deleted]初中平几知识：如果一个点钝角大于120度，这个点就是费马点，否则三角形内部一个到三边成三个120度的点是费马点。要求费马点，做正三角形辅助线就行，证明也差不多。把这个糊到三分套三分上去就直接过了
