企业官网建设流程全解析

切蓝然后回家路上摔了一跤🤔，运气守恒？

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 MB，1 MB = 1,048,576 字节，除以两个点为524,288。

即 M 最大为，实际上因为拓扑过程中就路径压缩，M 会更小。

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 66000; vector<int> 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]; } } queue<int> 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 即可。

#include<bits/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]; map<int, 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博客