2023年CCPC秦皇岛站 补题记录

Problem A. 贵校是构造王国吗I（签到+思维）

• 每一行取 [i, i] 和 [i, i + 1] 即可（最后一行注意特判），最后多余的随便填，要注意不能建二维矩阵+最后随便填的时候避开 [n,1]（因为这两点vp的时候吃了两发罚时…）

#include <bits/stdc++.h>using namespace std;#define int long longtypedef pair<int, int> PII;void solve()
{int n, k; cin >> n >> k;int idx = 0;vector<PII> ans(k + 1);for (int i = 1; i <= n; i ++ ){ans[ ++ idx] = {i, i};if (i != n) ans[++ idx] = {i, i + 1};}ans[ ++ idx] = {n, 1};for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= n; j ++ ){if (idx == k) break;if (i != j && i + 1 != j && !(i == n && j == 1)) ans[ ++ idx] = {i, j};}if (idx == k) break;}for (int i = 1; i <= k; i ++ ) cout << ans[i].first << ' ' << ans[i].second << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}return 0;
}

Problem C. 回文字符串（回文自动机+字符串哈希+二分）

• 因为这题学会了PAM，全网找不到一份ac代码，交了37发总算给我过了
• 思路参考题解，代码注释很详细
  
  

#include <bits/stdc++.h>using namespace std;#define int long longtypedef pair<int, int> PII;struct PAM
{/*- 传入字符串下标从0开始- 本质不同的回文子串个数- 所有回文子串个数- 每种回文串出现的次数 cnt- 每种回文串的长度 len- 以下标 i 为结尾的回文串的个数 sed- 每个回文串在原串中出现的末尾位置 record*/const static int N = 5e5 + 10;string s;int n;vector<vector<int>> nxt;vector<int> fail; // 当前节点最长回文后缀的节点vector<int> len; // 当前节点表示的回文串的长度vector<int> cnt; // 当前节点回文串的个数， 在getcnt后可得到全部vector<int> sed; // 以当前节点为后缀的回文串的个数vector<int> record; // 每个回文串在原串中出现的位置vector<int> ump; // 以原串每个位置结尾的最长回文串结点编号int tot; // 节点个数int last; // 上一个节点PAM(string ss) : s(ss), n(ss.size()), tot(0), ump(n + 1){build(ss);insert();}int newnode(int lenx){nxt.emplace_back();for (int i = 0; i < 26; i++) nxt[tot].push_back(0);sed.push_back(0); cnt.push_back(0); fail.push_back(0); record.push_back(0);len.push_back(lenx);return tot;}void build(string ss){tot = 0;newnode(0);tot = 1, last = 0;newnode(-1);fail[0] = 1;n = ss.size();s = " " + ss;}int getfail(int x, int n){while (n - len[x] - 1 <= 0 || s[n - len[x] - 1] != s[n])x = fail[x];return x;}void insert(char cc, int pos){int c = cc - 'a';int p = getfail(last, pos);if (!nxt[p][c]){tot++;newnode(len[p] + 2);fail[tot] = nxt[getfail(fail[p], pos)][c];len[tot] = len[p] + 2;sed[tot] = sed[fail[tot]] + 1;nxt[p][c] = tot;}last = nxt[p][c];cnt[last]++;record[last] = pos;if (len[last] > len[ump[pos]]) ump[pos] = last;}void insert(){for (int i = 1; i <= n; i++) insert(s[i], i);get_cnt();}void get_cnt(){for (int i = tot; i > 0; i--)cnt[fail[i]] += cnt[i];}
};struct string_hash
{const int nn;const int Base1 = 131, MOD1 = 1e9 + 7;const int Base2 = 13331, MOD2 = 1e9 + 9;vector<int> ha1, ha2, pow1, pow2;vector<int> rha1, rha2;string_hash(const string &ss) : nn(ss.size()), ha1(nn + 1), ha2(nn + 1), pow1(nn + 1), pow2(nn + 1), rha1(nn + 1), rha2(nn + 1){pow1[0] = pow2[0] = 1;for(int i = 1; i <= nn; i++){pow1[i] = pow1[i - 1] * Base1 % MOD1;pow2[i] = pow2[i - 1] * Base2 % MOD2;}for(int i = 1; i <= nn; i++){ha1[i] = (ha1[i - 1] * Base1 + ss[i - 1]) % MOD1;ha2[i] = (ha2[i - 1] * Base2 + ss[i - 1]) % MOD2;rha1[i] = (rha1[i - 1] * Base1 + ss[nn - i]) % MOD1;rha2[i] = (rha2[i - 1] * Base2 + ss[nn - i]) % MOD2;}}PII get_hash(int l,int r){int res1 = ((ha1[r] - ha1[l - 1] * pow1[r - l + 1]) % MOD1 + MOD1) % MOD1;int res2 = ((ha2[r] - ha2[l - 1] * pow2[r - l + 1]) % MOD2 + MOD2) % MOD2;return {res1, res2};}PII get_rhash(int l, int r){int res1 = ((rha1[nn - l + 1] - rha1[nn - r] * pow1[r - l + 1]) % MOD1 + MOD1) % MOD1;int res2 = ((rha2[nn - l + 1] - rha2[nn - r] * pow2[r - l + 1]) % MOD2 + MOD2) % MOD2;return {res1, res2};}bool is_palindrome(int l, int r)//判断ss[l, r]是否为回文串{return get_hash(l, r) == get_rhash(l, r);}
};void solve()
{int n, m; cin >> n;string s; cin >> s;string rs = s;reverse(rs.begin(), rs.end());PAM pam1(s), pam2(rs);string_hash sh(s), shr(rs);// st[i][j] 从结点i沿fail往上跳2^j步到达的结点vector<vector<int>> st1(pam1.tot + 1, vector<int>(32));vector<vector<int>> st2(pam2.tot + 1, vector<int>(32));auto init = [&](PAM &pam, vector<vector<int>> &st) // 预处理pam倍增{int n = pam.tot;for (int i = 0; i <= n; i ++ ) st[i][0] = pam.fail[i];for (int j = 1; j <= 31; j ++ ){for (int i = 1; i <= n; i++){st[i][j] = st[st[i][j - 1]][j - 1];}}};init(pam1, st1); init(pam2, st2);cin >> m;while (m -- ){int l, r; cin >> l >> r;// 子串本身回文 不需要进行操作if (sh.is_palindrome(l, r)){cout << 0 << ' ' << 0 << '\n';continue;}// 子串非回文串// step1 二分+哈希找到区间最长对称前后缀auto cal_max_dc = [&](int x, int y) // 返回区间最长对称前后缀的长度{int l = 0, r = y - x + 1;while (l < r){int mid = l + r + 1 >> 1;if (sh.get_hash(x, x + mid - 1) == sh.get_rhash(y - mid + 1, y)) l = mid;else r = mid - 1;}return r;};int len_max_dc = cal_max_dc(l, r);// step2 对于非对称区间[x,y] 找到最长回文前缀和后缀auto cal_max_pd = [&](PAM &pam, vector<vector<int>> &st, int x, int maxlen) // 返回以x位置结尾的长度不超过maxlen的最长后缀{int idx = pam.ump[x];for (int i = 31; i >= 0; i -- ){if (pam.len[st[idx][i]] > maxlen) idx = st[idx][i];}if (pam.len[idx] > maxlen) idx = pam.fail[idx];return pam.len[idx];};int x = l + len_max_dc, y = r - len_max_dc;// 最长回文前缀：即在后缀串里找以x结尾的最长回文后缀int nx = n - x + 1; // x映射成后缀串里的下标int len_pdx = cal_max_pd(pam2, st2, nx, y - x + 1);// 最长回文后缀：即在前缀串里找以y结尾的最长回文后缀int len_pdy = cal_max_pd(pam1, st1, y, y - x + 1);// step3 求[l,x-1]和[x,x+t]的lcp / [y-t,y]和[y+1,r]的lcpint minans = min((r - l + 1) - len_max_dc * 2 - len_pdx, (r - l + 1) - len_max_dc * 2 - len_pdy);int cnt = 0;auto cal_max_lcs = [&](PAM &pam, int pos1, int pos2, int flag, int maxlen) // 返回pam中[1,pos1][1,pos2]的最长公共后缀{int l = 1, r = maxlen;while (l < r){int mid = l + r + 1 >> 1;if (flag == 1){if (sh.get_hash(pos1 - mid + 1, pos1) == sh.get_hash(pos2 - mid + 1, pos2)) l = mid;else r = mid - 1;}else{if (shr.get_hash(pos1 - mid + 1, pos1) == shr.get_hash(pos2 - mid + 1, pos2)) l = mid;else r = mid - 1;}}return r;};if (len_pdx >= len_pdy) // 删[y-len+1,y] 找[y-len+1,y]和[y+1,r]的lcp{cnt ++ ;if (len_max_dc != 0 && s[(x + len_pdx) - 1] == s[(y + 1) - 1]) cnt += cal_max_lcs(pam2, n - (x + len_pdx) + 1, n - (y + 1) + 1, 2, r - y); }if (len_pdx <= len_pdy){cnt ++ ;if (len_max_dc != 0 && s[(x - 1) - 1] == s[(y - len_pdy) - 1]) cnt += cal_max_lcs(pam1, y - len_pdy, x - 1, 1, x - l);}cout << minans << ' ' << cnt << '\n';}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}return 0;
}

Problem D. 茶和咖啡（贪心+数据结构）

• 贪心考虑，先将优惠券按使用时限从小到大排序，对于每一个优惠券，我们都使用在他可以使用的天数中，价格最低的一个上（因为使用后我们就要对那一天的咖啡价格进行修改，所以需要支持单点修改和区间查询的数据结构）
• 下方代码使用线段树

#include <bits/stdc++.h>using namespace std;#define int long longtypedef pair<int, int> PII;struct Segment_Tree
{// 定义后读入数组a build(1, 1, n)后即可直接使用int n; // 数组长度vector<int> a; // 原数组struct node{int l, r; // 左右边界// 需要维护的其他信息int minn, minpos;};vector<node> tr;Segment_Tree(int n) : n(n), a(n + 1), tr((n + 1) * 4) {};void pushup(node &u, node &lt, node &rt){u.l = lt.l, u.r = rt.r;// 维护其余信息if (lt.minn <= rt.minn){u.minn = lt.minn;u.minpos = lt.minpos;}else{u.minn = rt.minn;u.minpos = rt.minpos;}};void pushup(int u){pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);}void build(int u, int l, int r){tr[u] = {l, r};if (l == r){tr[u].minn = a[l];tr[u].minpos = l;return;}int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u); // 根据具体情况有时可以舍去}// 单点修改：a[pos] += xvoid modify(int u, int pos, int x){if (tr[u].l == pos && tr[u].r == pos){tr[u].minn += x;return;}int mid = tr[u].l + tr[u].r >> 1;if (pos <= mid) modify(u << 1, pos, x);else modify(u << 1 | 1, pos, x);pushup(u);}// 区间查询 返回对应区间的node结点node query(int u, int l, int r){if (tr[u].l >= l && tr[u].r <= r) return tr[u];int mid = tr[u].l + tr[u].r >> 1;if (r <= mid) return query(u << 1, l, r);else if (l > mid) return query(u << 1 | 1, l, r);else{node res;auto lt = query(u << 1, l, mid);auto rt = query(u << 1 | 1, mid + 1, r);pushup(res, lt, rt);return res;}}
};void solve()
{int n, m; cin >> n >> m;Segment_Tree sg(n);for (int i = 1; i <= n; i ++ ) cin >> sg.a[i];sg.build(1, 1, n);vector<PII> b(m + 1);for (int i = 1; i <= m; i ++ ) cin >> b[i].first >> b[i].second;sort(b.begin() + 1, b.end());for (int i = 1; i <= m; i ++ ){auto res = sg.query(1, 1, b[i].first);sg.modify(1, res.minpos, -b[i].second);}priority_queue<int, vector<int>, greater<int>> pq;for (int i = 1; i <= n; i ++ ) pq.push(sg.query(1, i, i).minn);int ans = 0;while (pq.size()){ans += pq.top();pq.pop();cout << ans << ' ';}cout << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}return 0;
}

Problem F. 质数之谜（dp）

• dp[i][j] 表示前 i 个数符合条件 第 i 个数状态为 j 的最小代价
• j=0 不变 j=1 变为1 j=2 变为偶数 j=3 变为非1奇数

#include <bits/stdc++.h>using namespace std;#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n; cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];// dp[i][j]: 前i个数符合条件 第i个数状态为j的最小代价// j=0 不变  j=1 变为1  j=2 变为偶数  j=3 变为非1奇数vector<vector<int>> dp(n + 1, vector<int>(4, INF));dp[1][0] = 0, dp[1][1] = dp[1][2] = dp[1][3] = 1;for (int i = 1; i < n; i ++ ){auto is_prime = [&](int x){for (int i = 2; i * i <= x; i ++ ){if (x % i == 0) return false;}return true;};// a[i]不改变if (is_prime(a[i] + a[i + 1])) dp[i + 1][0] = min(dp[i + 1][0], dp[i][0]);if (is_prime(a[i] + 1)) dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + 1);if (a[i] & 1) dp[i + 1][2] = min(dp[i + 1][2], dp[i][0] + 1);else dp[i + 1][3] = min(dp[i + 1][3], dp[i][0] + 1);// a[i]变为1if (is_prime(1 + a[i + 1])) dp[i + 1][0] = min(dp[i + 1][0], dp[i][1]);dp[i + 1][2] = min(dp[i + 1][2], dp[i][1] + 1);dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1);// a[i]变为偶数if (a[i + 1] & 1) dp[i + 1][0] = min(dp[i + 1][0], dp[i][2]);dp[i + 1][1] = min(dp[i + 1][1], dp[i][2] + 1);dp[i + 1][3] = min(dp[i + 1][3], dp[i][2] + 1);// a[i]变为非1奇数if (a[i + 1] % 2 == 0) dp[i + 1][0] = min(dp[i + 1][0], dp[i][3]);dp[i + 1][2] = min(dp[i + 1][2], dp[i][3] + 1);}cout << min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]}) << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}return 0;
}

Problem G. 最大路径（签到）

#include <bits/stdc++.h>using namespace std;#define int long longvoid solve()
{int n, m; cin >> n >> m;vector<int> a(n + 1), b(m + 1);int ans = 0;for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 1; i <= m; i ++ ) cin >> b[i];for (int i = 2; i <= n; i ++ ) ans += labs(a[i] - a[i - 1]);for (int i = 2; i <= m; i ++ ) ans += labs(b[i] - b[i - 1]);cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}return 0;
}

Problem I. 数据结构假象（线段树合并）

• 思路参考官方题解，用的线段树合并

#include <bits/stdc++.h>using namespace std;#define int long longconst int N = 5e5 + 5;struct Node
{int ch[2];int val;
} tr[N * 20];
int rt[N];
stack<int> pool;
int tot;// 新建结点 返回结点编号
int newnode()
{if (pool.empty()){// tr.emplace_back();return (++ tot);}else{int res = pool.top(); pool.pop();return res;}
}
// 删除结点u
void del(int u)
{pool.push(u);tr[u].ch[0] = tr[u].ch[1] = tr[u].val = 0;
}
// 单点修改: 加x个pos (当前结点为u 表示范围为[l,r])
void modify(int &u, int l, int r, int pos, int x)
{if (!u) u = newnode();tr[u].val += x;if (l == r) return;int mid = l + r >> 1;if (pos <= mid) modify(tr[u].ch[0], l, mid, pos, x);else modify(tr[u].ch[1], mid + 1, r, pos, x);
}
// 区间查询: 返回[lq,rq]内数值个数 (当前结点为u 表示范围为[l,r])
int query(int u, int l, int r, int lq, int rq)
{if (rq < l || lq > r) return 0;if (lq <= l && rq >= r) return tr[u].val;int mid = l + r >> 1;return query(tr[u].ch[0], l, mid, lq, rq) + query(tr[u].ch[1], mid + 1, r, lq, rq);
}
// 返回第k小的值
int kth(int u, int l, int r, int k)
{if (l == r) return l;int mid = l + r >> 1;if (tr[tr[u].ch[0]].val >= k) return kth(tr[u].ch[0], l, mid, k);else return kth(tr[u].ch[1], mid + 1, r, k - tr[tr[u].ch[0]].val);
}
// 合并结点ab
int merge(int a, int b)
{if (!a || !b) return a + b;tr[a].val += tr[b].val;tr[a].ch[0] = merge(tr[a].ch[0], tr[b].ch[0]);tr[a].ch[1] = merge(tr[a].ch[1], tr[b].ch[1]);del(b);return a;
}
// 分裂以x为根的子树为xy两棵树 其中x的大小是k
void split(int x, int &y, int k)
{if (!x) return;y = newnode();int v = tr[tr[x].ch[0]].val;if (k > v) split(tr[x].ch[1], tr[y].ch[1], k - v);else swap(tr[x].ch[1], tr[y].ch[1]);if (k < v) split(tr[x].ch[0], tr[y].ch[0], k);tr[y].val = tr[x].val - k;tr[x].val = k;
}void solve()
{int n, m, k; cin >> n >> m >> k;vector<int> a(n + 1), rst(1, -1), mod(1, -1);for (int i = 1; i <= n; i ++ ){cin >> a[i];rst.push_back(a[i] / k), mod.push_back(a[i] % k + 1);}// 离散化sort(rst.begin(), rst.end()); rst.erase(unique(rst.begin(), rst.end()), rst.end());sort(mod.begin(), mod.end()); mod.erase(unique(mod.begin(), mod.end()), mod.end());vector<int> sz(rst.size()); // sz[i]表示rst[i]的个数vector<int> pfx(rst.size()); // sz的前缀和for (int i = 1; i <= n; i ++ ){int id1 = lower_bound(rst.begin(), rst.end(), a[i] / k) - rst.begin();int id2 = lower_bound(mod.begin(), mod.end(), a[i] % k + 1) - mod.begin();sz[id1] ++ ;modify(rt[id1], 1, mod.size() - 1, id2, 1);}for (int i = 1; i < rst.size(); i ++ ) pfx[i] = pfx[i - 1] + sz[i];int nw = rst.size() - 1, unop = 0;auto merge1 = [&](int nw) // 合并nw层和nw-1层{rt[nw - 1] = merge(rt[nw - 1], rt[nw]);sz[nw - 1] += sz[nw];pfx[nw - 1] += sz[nw];sz[nw] = 0;unop = 0;};while (m -- ){char c; int x;cin >> c >> x;if (c == 'C'){int yu = sz[nw] - unop; // 当前层还剩下的if (yu >= x) unop += x;else{// 把当前层剩下的都减掉 相当于整体往下减一层x -= sz[nw] - unop;if (nw > 1 && rst[nw] == rst[nw - 1] + 1) // 如果减一层能直接和下一层合并{merge1(nw -- );}else // 不能和下一层合并{rst[nw] -- ;}while (x){if (nw == 1) // 当前层为最底层{int cnt = x / sz[nw];rst[nw] -= cnt;unop = x % sz[nw];x = 0;}else // 还有下一层{int need = (rst[nw] - rst[nw - 1]) * sz[nw]; // 将当前层合并到下一层需要多少步操作if (x >= need) // 将当前层与下一层合并{x -= need;merge1(nw -- );}else // 当前层不能和下一层合并{int cnt = x / sz[nw];rst[nw] -= cnt;unop = x % sz[nw];x = 0;}}}}if (unop == sz[nw]){if (nw == 1 || rst[nw - 1] + 1 != rst[nw]){unop = 0;rst[nw] -- ;}else{rt[nw - 1] = merge(rt[nw - 1], rt[nw]);unop = 0;sz[nw - 1] += sz[nw]; pfx[nw - 1] += sz[nw];sz[nw] = 0;nw -- ;}}}else if (c == 'A'){int yu = sz[nw] - unop; // 当前层剩下的if (yu >= x) cout << rst[nw] * k + mod[kth(rt[nw], 1, mod.size() - 1, sz[nw] - x - unop + 1)] - 1 << '\n';else{int id = lower_bound(pfx.begin(), pfx.end(), n - x + 1) - pfx.begin();if (id >= nw - 1) // 答案在当前层的下一层{if (nw != 1 && rst[nw] == rst[nw - 1] + 1){int a = 0;split(rt[nw], a, sz[nw] - unop);rt[nw - 1] = merge(rt[nw - 1], a);sz[nw - 1] += unop; pfx[nw - 1] += unop;sz[nw] -= unop;x -= sz[nw];unop = 0;cout << rst[nw - 1] * k + mod[kth(rt[nw - 1], 1, mod.size() - 1, sz[nw - 1] - x + 1)] - 1 << '\n';}else{if (id == nw) // 说明答案在unop里{x -= sz[nw] - unop;cout << (rst[nw] - 1) * k + mod[kth(rt[nw], 1, mod.size() - 1, sz[nw] - x + 1)] - 1 << '\n';}else if (id == nw - 1) // 答案在nw-1段里{x -= sz[nw];cout << rst[nw - 1] * k + mod[kth(rt[nw - 1], 1, mod.size() - 1, sz[nw - 1] - x + 1)] - 1 << '\n';}}}else{x = n - x + 1 - pfx[id - 1];cout << rst[id] * k + mod[kth(rt[id], 1, mod.size() - 1, x)] - 1 << '\n';}}}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}return 0;
}

Problem J. 维克多词典（状压+记忆化）

• 只记录有效状态，对有效状态进行转移
• 什么叫有效状态呢：第一，一定要合法；第二，不能再往里加任何一个元素

#include <bits/stdc++.h>using namespace std;#define int long longconst int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, w; cin >> n >> w;vector<int> cnt(14);for (int i = 1; i <= n; i ++ ){int x; cin >> x;cnt[x] ++ ;}set<int> st, tmp;auto check1 = [&](int x, int y) // 状态x变为y是否为合法集合{int need = 0;for (int i = 0; i < 13; i ++ ){if (((x >> i) & 1) == 1 && ((y >> i) & 1) == 0) return false;else if (((x >> i) & 1) == 0 && ((y >> i) & 1) == 1){need += cnt[i + 1];if (need > w) return false;}}return true;};auto check2 = [&](int x, int y) // 状态x变为y是否为最大有效集合{int yu = w, minn = INF;for (int i = 0; i < 13; i ++ ){int xx = ((x >> i) & 1), yy = ((y >> i) & 1);if (xx == 1 && yy == 1) continue;else if (xx == 0 && yy == 0) minn = min(minn, cnt[i + 1]);else if (xx == 0 && yy == 1) yu -= cnt[i + 1];}if (yu >= minn) return false;else return true;};int ans = 1;for (int i = 0; i < (1ll << 13); i ++ ){if (!check1(0, i)) continue;if (!check2(0, i)) continue;if (i == ((1ll << 13) - 1)){cout << ans << '\n';return;}st.insert(i);}while (1){ans ++ ;tmp.clear();for (auto t : st){for (int i = 0; i < (1ll << 13); i ++ ){if (!check1(t, i)) continue;if (!check2(t, i)) continue;tmp.insert(i);}}st.clear();for (auto t : tmp){if (t == ((1ll << 13) - 1)){cout << ans << '\n';return;}st.insert(t);}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;while (t--){solve();}return 0;
}

Problem M. 生成树计数（树形dp）

• 思路参考官方题解

#include <bits/stdc++.h>using namespace std;#define int long long
const int mod = 998244353;void solve()
{int n; cin >> n;vector<vector<int>> g(n + 1);for (int i = 1; i < n; i ++ ){int u, v; cin >> u >> v;g[u].push_back(v), g[v].push_back(u);}vector<bool> p(n + 1), vis(n + 1);vector<int> dp1(n + 1), dp2(n + 1);function<void(int, int)> dfs = [&](int u, int fa){if (!p[u]){dp1[u] = 1, dp2[u] = 0;return;}dp1[u] = 0, dp2[u] = 1, vis[u] = true;for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i];if (j == fa) continue;dfs(j, u);dp1[u] = (dp1[u] * dp2[j] % mod + dp2[u] * dp1[j] % mod + 2 * dp1[u] * dp1[j] % mod) % mod;dp2[u] = (dp2[u] * dp2[j] % mod + 2 * dp2[u] * dp1[j] % mod) % mod;}};for (int i = 1; i < n; i ++ ){int x; cin >> x;p[x] = true;vis.assign(vis.size(), false);int ans = 1;for (int j = 1; j <= n; j ++ ){if (p[j] && !vis[j]){dfs(j, 0);ans = ans * dp1[j] % mod;}}cout << ans << '\n';}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}return 0;
}