时间安排

• $7:30$ 开题
• $7:30-7:35$ 看完 $T1$ 后尝试推一下，发现好像前缀和一下就做完了？？！然后就去写了。
• $7:55$ 调出来了，交上去过了。不到 $30min$ 切 $T1$。今天比较简单啊。
• $7:55-8:10$ 理解了 $T2$ 的题意。刚开始觉得好复杂，后来忽然发现只有路径上相邻两个元素在同一棵树上才有限制，如果不在那么是任意的。感觉变得很套路了。
• $8:10-10:40$：稳住心态，一点一点推式子，一步一步的将问题拆成小问题然后解决。中间有几步意识到自己想的有点问题，但是大方向是对的所以也修过来了。然后终于写完了，小样例没过！！虽然比较难调，但还是调过了。交上去，获得高贵的 $5pts$。
• $10:40-11:35$ 然后就去痛批 jsy 不给大样例。但是他没空所以就先去静态差错了。没查出来，所以就去对拍。写了个指数的暴力，交上去能过第一个点。先尝试手造一些小数据。然后发现两棵树的都过了，大于两棵树的都 $WA$ 了。思考后发现是每棵树卷积合并的时候假了。然后就去修锅，转化成正确的模型后感觉自己不太会 $n^2$ 复杂度的？？！！后来想了想发现容斥的思路可以优化到 $O(n^2)$，改了一下交上去直接过了！！！
• $11:35-12:30$ 还有将近 $1h$，想了想 $T3$ 的正解，发现没出思路。然后写了 $60pts$ 暴力，在写暴力的时候发现刚才想正解的方向都是错的。但是时间也不允许再去思考和实现正解了。

最终得分： 100 + 100 + 60 = 260

反思

• 调不出来时不要一直静态差错。有时候写一个暴力是很快的。当你有小数据去调试时应该会比较快调对或者意识到你哪里错了。
• 思考问题除了特别有思路，否则最好不要直接去思考正解。可以从部分分入手，这样会让你的方向变得明确。

题解

[六省联考 2017] 期末考试（贪心， 枚举）

题面

分析：
唐题。发现不愉悦值只和成绩最晚公布时间有关。直接枚举最晚公布时间可以贪心的调整， $O(1)$ 计算最小代价。复杂度线性。

CODE：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef __int128 Int;
const int N = 1e5 + 10;
LL A, B, C, st[N], stc[N], sb[N], sbc[N], res = 1e18;
int n, m, t[N], b[N], lim;
inline LL calc(int T) {Int ans = (Int)(1LL * T * stc[T] - st[T]) * C;if(ans > res) return res;LL ret = ans;if(1LL * m * T >= sb[lim]) ret += min(A, B) * (sb[lim] - sb[T] - (sbc[lim] - sbc[T]) * T);else ret += B * (sb[lim] - 1LL * m * T) + min(A, B) * (sb[lim] - sb[T] - (sbc[lim] - sbc[T]) * T - (sb[lim] - 1LL * m * T));return ret;
}
int main() {scanf("%lld%lld%lld", &A, &B, &C);scanf("%d%d", &n, &m);for(int i = 1; i <= n; i ++ ) {scanf("%d", &t[i]); lim = max(lim, t[i]);st[t[i]] += t[i]; stc[t[i]] ++;}for(int i = 1; i <= m; i ++ ) {scanf("%d", &b[i]); lim = max(lim, b[i]);sb[b[i]] += b[i]; sbc[b[i]] ++;}for(int i = 1; i <= lim; i ++ ) st[i] += st[i - 1], stc[i] += stc[i - 1];for(int i = 1; i <= lim; i ++ ) sb[i] += sb[i - 1], sbc[i] += sbc[i - 1];for(int T = 1; T <= lim; T ++ ) res = min(res, calc(T));cout << res << endl;return 0;
}

[JSOI2019] 神经网络（容斥， 组合计数， 树背包）

题面

题意：
给定 $m$ 棵树，第 $i$ 棵树有 $k_i$ 个结点。
除了这 $m$ 棵树的树边外，你要在任意两个不在同一棵树上的点 之间添加一条边，得到一张联通图 $G$。
你需要求出 $G$ 的 哈密顿回路 的数量。以第一棵树的 $1$ 号点为起点。

$\sum _{i=1}^m{k}_i\le 5000,1\le m\le 300,k_i\ge 1$。

分析：
假设得到了一条以 $1$ 为起点的哈密段回路 $R$，$R_i$ 表示第 $i$ 个经过的点的编号。我们来考虑对 $R$ 需要有什么限制。

发现对于路径上相邻的两个点 $R_i,R_{i+1}$，如果它们属于不同的树，那么这一对相邻就没有任何限制（两棵树之间的连边是完全二分图）。如果它们属于同一棵树，那么就必须要求 $R_i$ 和 $R_{i+1}$ 在树上相邻。

那么我们将 $R$ 分成若干极长连续段，每一段的点都在一棵树上，发现 $R$ 合法就等价于 每一段都对应树上的一条有向路径。

这告诉我们不同的树之间的限制是独立的。我们分别对每一棵树计算方案数，同时记录划分了多少段，然后不同的树之间卷积合并即可。

对一棵树相当于要求 将它划分成若干不交路径（每个点恰好属于一条路径）的方案数。这是一个很经典的问题，$dp$ 状态只需要记录子树内已经划分了多少条路径，根是否在一条半链 即可。转移就是经典的树背包卷积，复杂度 $O(k_i^2)$。

一个小细节就是长度 $\ge 2$ 的路径有两个方向，但是长度等于 $1$ 的路径只有一个方向，所以不太好求出路径条数之后再考虑方向对方案数的贡献。这个只要在 $dp$ 时每产生一条路径就把系数乘进去即可。

对于第一棵树也需要特殊处理！因为我们固定了 第一棵树的 $1$ 号点为起点，所以 $1$ 号点所在的路径上 $1$ 必须作为端点，并且这条路径不能调转方向。这个只需要特殊处理一下转移即可。

还有一个问题：我们要求的 回路，然后已经固定了第一段是第一棵树的 $1$ 所在路径。但是我们不知道最后一段是什么（还需要考虑后面树提供的段）。如果最后一段也是第一棵树的一条路径，那么需要保证最后一个点是能到 $1$ 的。

这个处理起来比较麻烦：只需要拿 不限制 $1$ 提供最后一段 的方案数 减去 钦定 $1$ 提供最后一段 的方案数，加上 钦定 $1$ 提供最后一段，并且最后一段要合法 的方案数即可。怎么钦定提供最后一段呢？将后面的段看作 插入前面段的间隔中，那么只要删掉最后一个间隔就能保证它提供最后一段了。怎么保证最后一段合法呢？发现第一段和最后一段恰好就构成了一条 不要求 $1$ 在端点的包含 $1$ 的路径。那么我们求出这样的路径划分数量，然后把 $1$ 所在的路径拆成两条即可，注意此时最后一段也不能调转方向。

除了第一个树，后面的都是相同的。考虑现在还有一个限制，就是 一棵树分成的段之间不能相邻。怎么处理这个呢？

容斥这个限制：对于第一棵树，相当于提供了若干空，你可以往这些空里面插其它树形成的段，但是一定要把这些空都插有。我们钦定 $i$ 个空最终没被插，然后乘上 $(-1{)}^i$ 的容斥系数，就变成有若干空，任意往里面插了。对于后面的树也类似：假设形成了 $x$ 段，那么钦定了 $t$ 段不合法后相当于就变成了 $x-t$ 个段，然后就是一个 $x_1+x_2+...+x_{x-t}=c$，$x_i\ge 0$ 的问题，可以组合数 $O(1)$ 计算方案，然后新增的空位数量恒定为 $x-t$。注意这里枚举树的段和钦定若干不合法是 $O(k_i^2)$，然后这一部分要和与之前的卷积分开枚举，复杂度就是 $O((\sum k_i{)}^2)$。

这样就做完了。时空复杂度 $O((\sum k_i{)}^2)$。

CODE：

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N = 5010;
typedef long long LL;
const LL mod = 998244353;
int m, n, sum, sz[N];
vector< int > E[N];
LL C[N][N], mi[N], fac[N], h[2][N], f[2][N][N], g[N][N], tg[N], tf[2][N]; // h[i][j] 表示考虑到了第 i 棵树，还有 j 个空位可以插的方案数。  f[x][i] 表示 x 在一条半链上, g[x][i] 表示在一条完整的链上
void dfs(int x, int fa, int p) { // 求一遍正常的链划分if(x == 1 && p == 1) {f[0][x][0] = 2; f[1][x][0] = 1;}else {f[0][x][0] = f[1][x][0] = 1; g[x][1] = 1;} sz[x] = 1;for(auto v : E[x]) {if(v == fa) continue;dfs(v, x, p); for(int i = 0; i <= sz[x] + sz[v]; i ++ ) tg[i] = tf[0][i] = tf[1][i] = 0;for(int i = 0; i <= sz[x]; i ++ ) {for(int j = 0; j <= sz[v]; j ++ ) {tg[i + j] = (tg[i + j] + g[x][i] * g[v][j] % mod) % mod; // g * g -> gtg[i + j + 1] = (tg[i + j + 1] + f[1][x][i] * f[1][v][j] % mod * ((x == 1 && p == 1) ? 1 : 2) % mod) % mod; // f * f -> gtf[0][i + j] = (tf[0][i + j] + f[0][x][i] * g[v][j] % mod) % mod; // f * g -> ftf[1][i + j] = (tf[1][i + j] + f[1][x][i] * g[v][j] % mod) % mod; // f * g -> ftf[1][i + j] = (tf[1][i + j] + f[0][x][i] * f[1][v][j] % mod) % mod; // f * f -> f}}for(int i = 0; i <= sz[x] + sz[v]; i ++ ) f[0][x][i] = tf[0][i], f[1][x][i] = tf[1][i], g[x][i] = tg[i];sz[x] += sz[v];}
}
LL tmp[N]; 
inline LL sign(int x) {return (x & 1) ? mod - 1 : 1;}
inline void solve(int p, int l) { // 处理第 p 棵树for(int i = 0; i <= n; i ++ ) for(int j = 0; j <= n; j ++ ) f[0][i][j] = f[1][i][j] = g[i][j] = 0;dfs(1, 0, p);// 现在 g[x][i] 表示把 x 的子树划分成 i 条链， 并且长度 >= 2 的要乘上 2 的系数if(p == 1) { // 特别处理 T_1， 这个还需要容斥一下保证满足段之间不相邻的限制， 容斥完就变成这些段任意了// 思路是总的 - 有 1 段在末尾的 + 有 1 段在末尾并且合法的。 for(int i = 1; i < n; i ++ ) tmp[i + 1] = g[1][i] * fac[i - 1] % mod;for(int i = 0; i <= n; i ++ ) f[1][1][i] = g[1][i] = 0;f[1][1][0] = 1, g[1][1] = 1; int nsz = 1;for(auto v : E[1]) {for(int i = 0; i <= nsz + sz[v]; i ++ ) tf[1][i] = tg[i] = 0;for(int i = 0; i <= nsz; i ++ ) {for(int j = 0; j <= sz[v]; j ++ ) {tf[1][i + j] = (tf[1][i + j] + f[1][1][i] * g[v][j] % mod) % mod;tg[i + j] = (tg[i + j] + g[1][i] * g[v][j] % mod) % mod;tg[i + j + 1] = (tg[i + j + 1] + f[1][1][i] * f[1][v][j] % mod) % mod; // 注意这里不能乘 2}}for(int i = 0; i <= nsz + sz[v]; i ++ ) f[1][1][i] = tf[1][i], g[1][i] = tg[i];nsz += sz[v];}for(int i = 1; i <= n; i ++ ) { // 枚举段数//~ cout << "RRR" << i << ' ' << g[1][i] << endl;for(int j = 0; j <= i - 1; j ++ ) { // 钦定 i - 1 个里面有 j 个最后没被插， 剩余随意h[1][i - j] = (h[1][i - j] + g[1][i] * fac[i - 1] % mod * sign(j) % mod * C[i - 1][j] % mod) % mod;}// 钦定在末尾的for(int j = 0; j <= i - 1; j ++ ) {h[1][i - 1 - j] = (h[1][i - 1 - j] + g[1][i] * fac[i - 1] % mod * (mod - 1) % mod * sign(j) % mod * C[i - 1][j] % mod) % mod;}// 合法的钦定在末尾的for(int j = 0; j <= i - 1; j ++ ) {h[1][i - 1 - j] = (h[1][i - 1 - j] + tmp[i] * sign(j) % mod * C[i - 1][j] % mod) % mod; // tmp[i] 表示有 i 段， 并且末尾与开头合法}}}else { // 这个就简单了， 只需要看 g[1][i]， 然后插板即可// 现在 h 的含义是 h_i 表示有 i 个空， 不要求最后它们都被插 for(int i = 1; i <= sz[1]; i ++ ) tmp[i] = 0;for(int i = 1; i <= sz[1]; i ++ ) { // g[1][i]LL v = g[1][i] * fac[i] % mod; // i 个元素// 钦定一些限制不成立for(int j = 0; j <= i - 1; j ++ ) {// 那么就合并成了 i - j 个元素了tmp[i - j] = (tmp[i - j] + v * C[i - 1][j] % mod * sign(j) % mod) % mod;}}for(int i = 1; i <= sz[1]; i ++ ) { // 只关心最后剩下几个元素， 加入它们一定会多 i 个空位for(int j = 1; j <= l; j ++ ) {h[p & 1][j + i] = (h[p & 1][j + i] + h[p - 1 & 1][j] * tmp[i] % mod * C[i + j - 1][j - 1] % mod) % mod;}}for(int i = 0; i <= l; i ++ ) h[p - 1 & 1][i] = 0;}
}
int main() {mi[0] = 1; for(int i = 1; i < N; i ++ ) mi[i] = (mi[i - 1] * 2) % mod;fac[0] = 1; for(int i = 1; i < N; i ++ ) fac[i] = fac[i - 1] * i % mod;for(int i = 0; i < N; i ++ ) for(int j = 0; j <= i; j ++ ) if(!j) C[i][j] = 1;else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;scanf("%d", &m); int now = 0;for(int i = 1; i <= m; i ++ ) {scanf("%d", &n); sum += n;for(int j = 1; j <= n; j ++ ) E[j].clear();for(int j = 1; j < n; j ++ ) {int u, v; scanf("%d%d", &u, &v); E[u].pb(v); E[v].pb(u);}solve(i, now); // 特殊处理 T_1now += n;}LL res = 0;for(int i = 0; i <= sum; i ++ ) res = (res + h[m & 1][i]) % mod;cout << res << endl;return 0;
}

[ZJOI2019] 语言（dsu on tree， 虚树， 结论）

题面

题意：
给定 一棵 $n$ 个点的树和 $m$ 条路径 $(s_i,t_i)$，其中第 $i$ 条路径上的点都 具有 $i$这种颜色。
对一个点 $x$，它能 访问 $y$ 当且仅当 $(x,y)$ 路径上的点都具有某种颜色 $c$。
你需要求出所有点对 $(u,v)$ 的数量，满足 $u<v$ 且 $u$ 能访问 $v$。

$1\le n,m\le 10^5$。

分析：
考虑一个暴力怎么写：先来计算有序对的数量，最后 $/2$ 就是无序对的数量。对每个 $x$ 分别计算它能访问多少个 $y$，可以将所有 经过 $x$ 的路径 拿出来，把路径上的点涂黑，那么黑点的数量减 $1$ 就是 $x$ 能访问的点数。

发现暴力等价于枚举 $x$，然后保留所有经过 $x$ 的路径的端点后建出 虚树，虚树的边数就是 $x$ 的答案。

有经典结论：任意点集的虚树周长等于按照 $dfs$ 序将点集中的点排序后，相邻两个点的距离之和（认为最后一个和第一个也是相邻的）。
这里的周长就是虚树的边数。

那么我们只要能维护出所有经过 $x$ 的路径的端点，按照 $dfs$ 序排序后的有序集合就可以支持加点，删点后快速更新答案。

将一条路径看作在两个端点处加入，在 $lca$ 处删除。然后直接上 $dsu$，开一个 $set$ 维护当前还保留的路径端点，每次往里 加入，删除点，增量修改答案。那么一个点上的所有路径信息显然会被处理 $\log n$ 次，每次加入/删除一个点复杂度 $O(\log n)$，总复杂度就是 $O(m{\log }^{2}n)$。

代码很好写，没啥细节。

CODE：

// dsu on tree 就是俩log
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m, s[N], t[N];
int dep[N], sz[N], big[N], fat[N][18], dfn[N], L[N], R[N], dfc, ID[N];
int cnt[N];
LL res, ans; // ans 表示当前维护的虚树大小
set< int > S; // 按照 dfn 排序
vector< int > E[N];
vector< int > Ad[N], De[N];
void dfs0(int x, int fa) {fat[x][0] = fa; for(int i = 1; i <= 17; i ++ ) fat[x][i] = fat[fat[x][i - 1]][i - 1];dep[x] = dep[fa] + 1; sz[x] = 1;for(auto v : E[x]) {if(v == fa) continue;dfs0(v, x); sz[x] += sz[v];if(sz[v] > sz[big[x]]) big[x] = v;}
}
void dfs1(int x, int fa) {dfn[x] = L[x] = ++ dfc; ID[dfc] = x;if(big[x]) dfs1(big[x], x);for(auto v : E[x]) {if(v == fa || v == big[x]) continue;dfs1(v, x);}R[x] = dfc;
}
inline int lca(int x, int y) {if(dep[x] < dep[y]) swap(x, y);for(int i = 17; i >= 0; i -- ) if(dep[fat[x][i]] >= dep[y]) x = fat[x][i];if(x == y) return x;for(int i = 17; i >= 0; i -- )if(fat[x][i] != fat[y][i]) x = fat[x][i], y = fat[y][i];return fat[x][0];
}
inline int dis(int x, int y) {return dep[x] + dep[y] - 2 * dep[lca(x, y)];}
inline LL calc(int x) { auto it = S.lower_bound(x);it ++;if(it == S.end()) it = S.begin();int nxt = (*it);return dis(ID[nxt], ID[x]);
}
inline void add(int x) {cnt[x] ++;if(cnt[x] != 1) return ;else {if(S.empty()) S.insert(dfn[x]);else { // 找到上一个auto it = S.lower_bound(dfn[x]);if(it == S.begin()) {it = S.end(); it --;}else it --;int o = (*it);ans -= calc(o);S.insert(dfn[x]);ans += calc(dfn[x]) + calc(o);}}
}
inline void del(int x) {cnt[x] -= 2; if(cnt[x] != 0) return ;if(S.size() == 1) S.erase(dfn[x]);else {		auto it = S.find(dfn[x]);if(it == S.begin()) {it = S.end(); it --;}else it --;int o = (*it);ans -= calc(dfn[x]) + calc(o);S.erase(dfn[x]);ans += calc(o);}
}
inline void Add(int x) {for(auto v : Ad[x]) add(s[v]), add(t[v]);} // 加入路径端点
inline void Del(int x) {for(auto v : De[x]) del(s[v]), del(t[v]);} // 删除路径端点
void dfs2(int x, int fa, bool keep) { // dus on treefor(auto v : E[x]) {if(v == fa || v == big[x]) continue;dfs2(v, x, false);}if(big[x]) dfs2(big[x], x, true);for(auto v : E[x]) { // 加入轻子树if(v == fa || v == big[x]) continue;for(int i = R[v]; i >= L[v]; i -- ) Add(ID[i]);for(int i = R[v]; i >= L[v]; i -- ) Del(ID[i]);}Add(x); res += ans; Del(x);if(!keep) {ans = 0; S.clear();for(int i = L[x]; i <= R[x]; i ++ ) for(auto v : Ad[ID[i]]) cnt[s[v]] = cnt[t[v]] = 0;}
}
int main() {scanf("%d%d", &n, &m);for(int i = 1; i < n; i ++ ) {int u, v; scanf("%d%d", &u, &v);E[u].pb(v); E[v].pb(u);}dfs0(1, 0);dfs1(1, 0);for(int i = 1; i <= m; i ++ ) {scanf("%d%d", &s[i], &t[i]);int lc = lca(s[i], t[i]);Ad[s[i]].pb(i); Ad[t[i]].pb(i);De[lc].pb(i);}dfs2(1, 0, 0);cout << res / 4 << endl;return 0;
}