精准预测
我们首先发现每个人每个时刻只有生死，所以我们可以建一个 2-sat 模型。每个人对应 \(T+1\) 个节点，表示这个人在每个时刻的生死。
那么，题目的条件可以直接在这个模型上面建图，还要注意第 \(t\) 秒死亡可推出第 \(t+1\) 秒死亡和第 \(t+1\) 秒存活能推出第 \(t\) 秒存活的两个隐藏条件。
这样子点数是 \(\mathcal O(nT)\) 的，不可接受。我们发现这张图有很多没用的点，我们只需要建出来：第 \(T+1\) 时刻的，或者被 \(m\) 个条件提及到的点即可。点数降至 \(\mathcal O(n+m)\)。
考虑计算答案，首先你不难发现建出的这张图是一个 DAG，假设 \(A(i,t)\) 表示第 \(i\) 个人在第 \(t\) 秒存活，\(D(i,t)\) 反之。那么如果 \(A(i,T+1)\to D(i,T+1)\)，也就是第 \(i\) 个点不能存活，这样的点我们不管（至于怎么找见下文）。我们任务就是找出每个可存活的点 \(u\)，\(A(u,T+1)\) 可以推出多少个可存活点的 \(D(*,T+1)\)。
首先这是 DAG 联通的问题，只能使用 bitset，但是直接开 bitset 开不下，这要求我们对分段求解。具体的我们每 \(B\) 个点一段，沿着拓扑序往回跑即可。
最终我们可以用一个 bitset \(ex\) 统计哪些点能够存活，我们只需要数 \(A(u,T+1)\) 和 \(ex\) 的与运算下的 \(1\) 个数即可。
取 \(B=2^{13}\) 可以通过。
神经网络
考虑哈密顿路径相关问题的经典做法：拆链。
考虑这个哈密顿路径和每棵树的交边，必然是若干的有向链。我们可以用 \(\mathcal O(k_i^2)\) 求出把这棵树划分成 \(i\) 条链的方案数。需要注意的是，除了单链，其他链都可以定向，有一个 \(2\) 的系数。
不妨假设我们已经钦定每个树贡献出来的链数，\(a_1,a_2,\dots,a_m\)。问题转化为：
有 \(\sum a_i\) 个有序小球，其中颜色 \(i\) 有 \(a_i\) 个。把这些小球排成一圈，要求相邻小球不同色，求方案数。
对于这个问题，我们可以容斥。具体的，我们把颜色 \(i\) 的小球钦定为 \(b_i\) 个链，假设这个容斥系数为 \((-1)^{a_i-b_i}H_{a_i}^{b_i}\)，其中 \(H_n^m\) 是把 \(n\) 个小球排成 \(m\) 个有区别队列的方案数，\(H_n^m=n!\times\dbinom{n-1}{m-1}\)。这之后我们去掉了相邻小球不同的限制，我们就可以通过背包求了。
对于这道题，有一个颜色 \(i\) 有多种 \(a_i\)，我们可以把这些 \(a_i\) 合并起来转移，复杂度是 \(\mathcal O((\sum k)^2)\) 的。
节日庆典
考虑 \(i\) 从小变大的时候，哪些 \(x\) 能作为预选答案。
首先不能存在 \(y\) 使得 \(S[y,i]\) 字典序严格小于 \(S[x,i]\)。这里严格小不能存在前缀关系。
你发现这样子预选答案还是很多。我们通过类似 border 理论的思想可以把这些东西变成 \(\mathcal O(\log n)\) 种。
你发现如果两个备选答案 \(x<y\) 满足 \(i-y>y-x\)，那么这个时候，可以假设 \(S[x,i]=A\dots AB\)，\(S[y,i]=A\dots AB\)（前者有 \(t\) 个 \(A\)，后者有 \(t-1\) 个 \(A\)）。
那你发现 \(S[y,i]\) 肯定不如 \(S[x,i],B\) 之一。于是 \(y\) 必然不能作为答案。
最后我们把预选答案集合缩成 \(\mathcal O(\log n)\) 个。我们只需要考虑如何快速比较这些被选元素的大小。即比较 \(x<y\)，\(S[x,i]+S[1,x-1],S[y,i]+S[1,y-1]\) 的大小。
应为备选集合的条件，所以 \(S[y,i]\) 应该是 \(S[x,i]\) 的前缀，不需要比较。
剩下就是比较 \(S[x+(i-y),i]+S[1,x-1]\) 和 \(S[1,y-1]\) 的大小。你发现两坨东西都是形如一个子序列和前缀比大小的样子，你直接用 exkmp 处理出每个后缀和原串的 lcp，就可以 \(\mathcal O(1)\) 比较其大小了。