【记录】「TJOI2012 + 2022」三道模拟赛/26.7.14

切蓝然后回家路上摔了一跤运气守恒P2597 [ZJOI2012] 灾难 - 洛谷 (luogu.com.cn)自己场切的第一道蓝说下思路。1.一开始想的点双联通从食物到消费者建边强行把有向图迁移成无向图求出割点后再跑一遍求子树大小调了半小时 20 分 GG。2.观察到 n 刚好是考虑带 log 的做法估计是 LCA。而 LCA 必须在树上进行题目给的图加了超级源点都不是树看来得重建一颗。3.答案应该也是子树大小树边来自于依赖关系。考虑点 x 对于点 y 的依赖即点 y 消失后点 x 就一定灭绝。当且仅当点 y 是点 x 所有食物的 LCA。4.一个个枚举点求食物 LCA 肯定不现实时间复杂度。因为原图有严格的层次关系考虑一层层拓扑当一个点的入度为 0就可以建立依赖并入队。5.最后在依赖树里求每个节点的子树大小 - 1。6.时间复杂度平均M 最大可以到。但题目说输入的文件大小不超过 1 MB1 MB 1,048,576 字节除以两个点为524,288。即 M 最大为实际上因为拓扑过程中就路径压缩M 会更小。#includebits/stdc.h using namespace std; typedef long long LL; const int N 66000; vectorint G[N], cg[N]; int f[N][25], rd[N], dep[N], bfa[N]; int LCA(int x, int y) { if ((x 0) || (y 0)) { return 0; } if (dep[x] dep[y]) { swap(x, y); } for (int i 20; i 0; i --) { if (dep[f[x][i]] dep[y]) { x f[x][i]; } } if (x y) { return x; } for (int i 20; i 0; i --) { if (f[x][i] ! f[y][i]) { x f[x][i]; y f[y][i]; } } return f[x][0]; } bool v[N]; int siz[N]; void dfst(int x) { siz[x] 1; v[x] 1; for (int y : cg[x]) { dfst(y); siz[x] siz[y]; } } queueint Q; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; memset(rd, 0, sizeof(rd)); for (int i 1; i n; i ) { bfa[i] i; int x; while (cin x) { if (x 0) { break; } G[x].push_back(i); rd[i] ; } } memset(dep, 0, sizeof(dep)); for (int i 0; i n; i ) { for (int j 0; j 20; j ) { f[i][j] -1; } } for (int i 1; i n; i ) if (rd[i] 0) { G[0].push_back(i); rd[i] ; } Q.push(0); while (!Q.empty()) { int x Q.front(); Q.pop(); for (int y : G[x]) if (rd[y]) { if (x 0) { f[y][0] 0; } else { if (f[y][0] -1) { f[y][0] x; } else { if (f[y][0] ! 0) { f[y][0] LCA(x, f[y][0]); } } } rd[y] --; if (rd[y] 0) { Q.push(y); cg[f[y][0]].push_back(y); dep[y] dep[f[y][0]] 1; for (int i 1; i 20; i ) { f[y][i] f[f[y][i - 1]][i - 1]; } } } } memset(v, 0, sizeof(v)); memset(siz, 0, sizeof(siz)); for (int i 1; i n; i ) if (v[i] 0) { dfst(i); } for (int i 1; i n; i ) { cout (siz[i] - 1) \n; } return 0; }P2173 [ZJOI2012] 网络 - 洛谷 (luogu.com.cn)咱也没学过动态树啊那就学把。【题解】动态树 LCT 模板没学过 Splay 人士友好-CSDN博客按颜色分搞很多 splay 即可。#includebits/stdc.h using namespace std; const int N 1e4 10; struct node { int ch[2], fa, sum, v, tag; node () { ch[0] ch[1] fa sum v tag 0; } }; #define lc(p) tr[p].ch[0] #define rc(p) tr[p].ch[1] #define fa(p) tr[p].fa #define notrt(p) ((lc(fa(p)) p) || (rc(fa(p)) p)) struct LCT { node tr[N]; void pushup(int p) { int mx tr[p].v; mx max(mx, max(tr[lc(p)].sum, tr[rc(p)].sum)); tr[p].sum mx; } void pushdown(int p) { if (tr[p].tag) { swap(lc(p), rc(p)); tr[lc(p)].tag ^ 1; tr[rc(p)].tag ^ 1; tr[p].tag 0; } } void pushall(int p) { // 下发懒标记 if (notrt(p)) { pushall(fa(p)); } pushdown(p); } void rotate(int x) { int y fa(x); int z fa(y); int k rc(y) x; if (notrt(y)) { tr[z].ch[rc(z) y] x; } fa(x) z; tr[y].ch[k] tr[x].ch[k ^ 1]; fa(tr[x].ch[k ^ 1]) y; tr[x].ch[k ^ 1] y; fa(y) x; pushup(y); pushup(x); } void splay(int x) { // 将 x 旋转至根节点 pushall(x); // 操作前先下发懒标记 while (notrt(x)) { int y fa(x), z fa(y); if (notrt(y)) { if ((rc(y) x) ^ (rc(z) y)) { rotate(x); } else { rotate(y); } } rotate(x); } } void access(int x) { for (int y 0; x; ) { splay(x); // 先使 x 伸展至根节点 rc(x) y; pushup(x); // 改了边指向后一定要更新 y x; x fa(x); } } void makert(int x) { access(x); splay(x); tr[x].tag ^ 1; } void split(int x, int y) { makert(x); access(y); splay(y); } int findrt(int x) { access(x); splay(x); while(lc(x)) { pushdown(x); x lc(x); } splay(x); return x; } void link(int x, int y) { makert(x); if (findrt(y) ! x) { fa(x) y; } } void cut(int x, int y) { makert(x); if (findrt(y) x fa(y) x !lc(y)) { fa(y) 0; pushup(x); } } void change(int x, int y) { splay(x); tr[x].v y; pushup(x); } }; LCT tr[15]; int rd[15][N]; mapint, int mp[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int n, m, C, K; cin n m C K; for (int i 1; i n; i ) { int v; cin v; for (int j 1; j C; j ) { tr[j].change(i, v); } } memset(rd, 0, sizeof(rd)); for (int i 1; i m; i ) { int x, y, w; cin x y w; w ; mp[x][y] mp[y][x] w; rd[w][x] ; rd[w][y] ; tr[w].link(x, y); } for (int i 1; i K; i ) { int opt; cin opt; if (opt 0) { int x, y; cin x y; for (int j 1; j C; j ) { tr[j].change(x, y); } } else if (opt 1) { int x, y, w; cin x y w; w ; if (!mp[x][y]) { cout No such edge.\n; } else if ((rd[w][x] 2 || rd[w][y] 2) mp[x][y] ! w) { cout Error 1.\n; } else if (tr[w].findrt(x) tr[w].findrt(y) mp[x][y] ! w) { cout Error 2.\n; } else { int last mp[x][y]; rd[last][x] --; rd[last][y] --; tr[last].cut(x, y); rd[w][x] ; rd[w][y] ; tr[w].link(x, y); mp[x][y] mp[y][x] w; cout Success. \n; } } else { int c, x, y; cin c x y; c ; if (tr[c].findrt(y) ! tr[c].findrt(x)) { cout -1\n; continue; } tr[c].split(x, y); cout tr[c].tr[y].sum \n; } } return 0; }https://www.luogu.com.cn/problem/P8329呜呜呜。【题解】P4500 [ZJOI2018] 树Mobius 反演-CSDN博客