小明の雜貨鋪

The 2022 ICPC Asia Shenyang Regional Contest (The 1st Universal Cup, Stage 1: Shenyang)

第九届中国大学生程序设计竞赛（哈尔滨）

第九届中国大学生程序设计竞赛（深圳）

为叙述方便，树上节点的 上方 指朝向根的方向， 下方 指朝向叶的方向。 Lowest Common Ancestor Lowest Common Ancestor 倍增算法 预处理时间复杂度 Θ(nlog⁡n)\Theta(n\log n)Θ(nlogn)，查询 Θ(log⁡n)\Theta(\log n)Θ(logn)。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546/* 前向星 */struct Edge { int nxt, to, w;};vector<Edge> E;int head[N], Log2[N], fa[88][N], dep[N], w[N];inline void add(int u, int v, int w) { E.push_back({ head[u], v, w }); head[u] = E.size() -...

Bipartite Graph 二分图 中的点由两个集合组成，且两个集合内部没有边。二分图不存在长度为奇数的环。 Check whether a given graph is Bipartite or not (Backtracking algorithm m coloring problem) 如果两个集合中的点分别染成黑色和白色，二分图中的每一条边都一定是连接一个黑色点和一个白色点。 1234567891011121314151617vector<int> E[N];int color[N];bool bipartite(int u) { // 判断是否是二分图 for (auto v : E[u]) { if (color[v] == color[u]) return 0; // 颜色冲突 if (color[v] == 0) { color[v] = -color[u]; if (!bipartite(v)) return 0; //...

Minimum Spanning Tree 构建最小生成树，求最小生成树的边权之和。 Kruskal (DSU) 思路 按边权从小到大的顺序开始合併连通图，如果没有环，那么它一定是最小生成树的一条边。时间复杂度 Θ(mlog⁡m)\Theta(m\log m)Θ(mlogm)，空间复杂度 Θ(m)\Theta(m)Θ(m)。 12345678910111213141516171819202122232425int fa[N];inline void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }inline void uno(int x, int y) { fa[find(x)] = find(y); }void eachT() { int n = read(); init(n); ...