- 给定一棵 \(n\) 个节点的树,一开始所有边都是蓝色的。每次选择一条所有边都是蓝色的路径,删掉其中一条边,然后在路径的两个端点之间连一条红边。求最后能不能得到目标形态(都是红边)的树。
- \(n \leq 10^5\)。
链覆盖
把所有选择的路径都覆盖一遍,那么第一次删除的边就是只覆盖了一次的边,删掉对应路径后,再取只覆盖了一次的边……以此类推,这种操作如果能进行 \(n-1\) 次就说明可行。
只有链操作,树剖或者LCT之类的随便写。
#include <bits/stdc++.h>
#define perr(a...) fprintf(stderr, a)
#define dbg(a...) perr("\033[32;1m"), perr(a), perr("\033[0m")
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(1e5 + 5);
int n;
std::vector<int> g[N];
int fa[N], in[N], siz[N], son[N], top[N], dep[N];
void dfs1(int x) {
siz[x] = 1;
for (int y : g[x]) {
if (y == fa[x]) continue;
fa[y] = x;
dep[y] = dep[x] + 1;
dfs1(y);
siz[x] += siz[y];
if (siz[y] > siz[son[x]]) son[x] = y;
}
}
void dfs2(int x) {
in[x] = ++in[0];
if (!son[x]) return;
top[son[x]] = top[x];
dfs2(son[x]);
for (int y : g[x]) {
if (y == fa[x] || y == son[x]) continue;
top[y] = y;
dfs2(y);
}
}
PII min[N << 2], e[N];
int val[N << 2], add[N << 2];
#define ls o << 1
#define rs o << 1 | 1
inline void pushup(int o) {
min[o] = std::min(min[ls], min[rs]);
}
inline void pushdown(int o) {
if (add[o]) {
add[ls] += add[o], add[rs] += add[o];
min[ls].first += add[o], min[rs].first += add[o];
add[o] = 0;
}
}
void del(int o, int l, int r, int x) {
if (l == r) { min[o].first = 1e9; return; }
pushdown(o);
int m = l + r >> 1;
x <= m ? del(ls, l, m, x) : del(rs, m + 1, r, x);
pushup(o);
}
void update(int o, int l, int r, int x, int y, int z, int v) {
if (x <= l && r <= y) {
add[o] += z;
min[o].first += z;
val[o] ^= v;
return;
}
pushdown(o);
int m = l + r >> 1;
if (x <= m) update(ls, l, m, x, y, z, v);
if (y > m) update(rs, m + 1, r, x, y, z, v);
pushup(o);
}
int ask(int o, int l, int r, int x) {
if (l == r) return val[o];
int m = l + r >> 1;
pushdown(o);
return (x <= m ? ask(ls, l, m, x) : ask(rs, m + 1, r, x)) ^ val[o];
}
void build(int o, int l, int r) {
if (l == r) {
min[o] = {0, l};
return;
}
int m = l + r >> 1;
build(ls, l, m), build(rs, m + 1, r);
pushup(o);
}
void update(int x, int y, int z, int v) {
for (; top[x] ^ top[y]; x = fa[top[x]]) {
if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
update(1, 2, n, in[top[x]], in[x], z, v);
}
if (x == y) return;
if (dep[x] > dep[y]) std::swap(x, y);
update(1, 2, n, in[x] + 1, in[y], z, v);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
for (int i = 1, x, y; i < n; i++) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
dfs1(1), top[1] = 1, dfs2(1);
build(1, 2, n);
for (int i = 1; i < n; i++) {
std::cin >> e[i].first >> e[i].second;
update(e[i].first, e[i].second, 1, i);
}
for (int i = 1; i < n; i++) {
if (min[1].first != 1) return puts("NO"), 0;
int x = min[1].second, y = ask(1, 2, n, x);
assert(y);
auto [u, v] = e[y];
update(u, v, -1, y);
del(1, 2, n, x);
}
puts("YES");
return 0;
}
启发式合并
对于第一棵树,最终状态是边都被删光了,只剩 \(n\) 个点。
倒着考虑,删边变成加边,具体点就是每次选择两个不连通的点在它们之间加边,对应在第二棵树上就是删一条端点分别在两个联通块内的边。
要在两棵树中分别找到这两条边,他们的共同点是连接了同样的两个联通块。
用并查集维护联通块,维护联通块连向外面的点集,用 std::map
统计两端点在不同联通块的边的个数。
#include <bits/stdc++.h>
#define perr(a...) fprintf(stderr, a)
#define dbg(a...) perr("\033[32;1m"), perr(a), perr("\033[0m")
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::vector<int>> g(n);
std::map<PII, int> p;
std::queue<PII> q;
std::vector<int> fa(n);
std::iota(fa.begin(), fa.end(), 0);
auto find = [&](int x) {
while (fa[x] != x) x = fa[x] = fa[fa[x]];
return x;
};
for (int i = 2, x, y; i < n + n; i++) {
std::cin >> x >> y;
x--, y--;
if (x > y) std::swap(x, y);
g[x].push_back(y), g[y].push_back(x);
if (++p[PII(x, y)] == 2) q.emplace(x, y);
}
for (int i = 1; i < n; ) {
if (q.empty()) return puts("NO"), 0;
auto [x, y] = q.front();
q.pop();
x = find(x), y = find(y);
if (p[PII(x, y)] < 2) continue;
assert(x != y);
if (g[x].size() > g[y].size()) std::swap(x, y);
fa[x] = y;
for (int v : g[x]) {
v = find(v);
if (v == y) continue;
--p[std::minmax(x, v)];
if (++p[std::minmax(y, v)] == 2) q.push(std::minmax(y, v));
g[y].push_back(v);
}
i++;
}
puts("YES");
return 0;
}