時間安排

• $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;
}