没报上名 /yun。

1

先看的括号树。一开始直接把 ( 看作 $1$，) 看作 $-1$，然后求 $1$ 到 $i$ 的路径上区间和为 $0$ 的区间个数。

但是发现这是不对的，因为还要保证任意时刻前缀和 $\ge$ 起点的前缀和。

所以重新考虑。这里就不太好。

然后对于链可以进行括号匹配来统计，直接求出 $f_i$ 表示以 $i$ 为结尾的数量，然后做前缀和即可求出。

然后考虑转移到树上，其实还是可以看作一条链，只不过把别的链上的贡献去除掉即可。

2

然后开的纪念品。一开始考虑了一个暴力，但是发现读错题了，有多种物品，所以重新考虑。

手玩样例然后注意到了持续持有一个物品多天等价于我在下一天卖了然后再买入。

所以直接 dp 就行。

3

然后看的加工零件。因为是和相邻的有关，所以答案和奇偶性有关。

然后发现我要提供原材料首先我的距离必须 $\leq L$。其次就是这个点到询问点的距离的奇偶性必须和 $L$ 相同，所以跑一遍 bfs 预处理 $1$ 到其他所有点奇数长度的最短路，偶数长度的最短路然后判断即可。

4

开的 E 家的饭。首先形式化题意：有 $n \times m$ 的网格，每行至多选 $1$ 个，每列至多选 $\lfloor \frac{m}{2} \rfloor$ 个，然后不能不选，求方案数。

由于至多选的个数为 $\lfloor \frac{m}{2} \rfloor$，所以只能有一种物品不合法。那就考虑容斥。

直接考虑了一个暴力 dp，设 $f_{i,j,k}$ 表示前 $i$ 种方式，一共选了 $j$ 个，不合法的物品选了 $k$ 个的方案。

转移 $O(n^3)$ 的，做 $m$ 次，有 $84$ pts。

赛后看的题解，就是注意到我们只关心 $j,k$ 的相对大小，所以直接把 $j,k$ 放到一维里，维护差值 dp。时间复杂度 $O(n^2m)$