Donghyun’s new social network service (SNS) contains $n$ users numbered $1, 2, \ldots, n$. Internally, their network is a tree graph, so there are $n-1$ direct connections between each user. Each user can reach every other users by using some sequence of direct connections. From now on, we will denote this primary network as $T_1$.
To prevent a possible server breakdown, Donghyun created a backup network $T_2$, which also connects the same $n$ users via a tree graph. If a system breaks down, exactly one edge $e \in T_1$ becomes unusable. In this case, Donghyun will protect the edge $e$ by picking another edge $f \in T_2$, and add it to the existing network. This new edge should make the network be connected again.
Donghyun wants to assign a replacement edge $f \in T_2$ for as many edges $e \in T_1$ as possible. However, since the backup network $T_2$ is fragile, $f \in T_2$ can be assigned as the replacement edge for at most one edge in $T_1$. With this restriction, Donghyun wants to protect as many edges in $T_1$ as possible.
Formally, let $E(T)$ be an edge set of the tree $T$. We consider a bipartite graph with two parts $E(T_1)$ and $E(T_2)$. For $e \in E(T_1), f \in E(T_2)$, there is an edge connecting $\{e, f\}$ if and only if graph $T_1 – \{e\} + \{f\}$ is a tree. You should find a maximum matching in this bipartite graph.Input
The first line contains an integer $n$ ($2 \le n \le 250\,000$), the number of users.
In the next $n-1$ lines, two integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$) are given. Those two numbers denote the indices of the vertices connected by the corresponding edge in $T_1$.
In the next $n-1$ lines, two integers $c_i$, $d_i$ ($1 \le c_i, d_i \le n$) are given. Those two numbers denote the indices of the vertices connected by the corresponding edge in $T_2$.
It is guaranteed that both edge sets form a tree of size $n$.Output
In the first line, print the number $m$ ($0 \leq m < n$), the maximum number of edges that can be protected.
In the next $m$ lines, print four integers $a_i, b_i, c_i, d_i$. Those four numbers denote that the edge $(a_i, b_i)$ in $T_1$ is will be replaced with an edge $(c_i, d_i)$ in $T_2$.
All printed edges should belong to their respective network, and they should link to distinct edges in their respective network. If one removes an edge $(a_i, b_i)$ from $T_1$ and adds edge $(c_i, d_i)$ from $T_2$, the network should remain connected. The order of printing the edges or the order of vertices in each edge does not matter.
If there are several solutions, you can print any.Examplesinput
4 1 2 2 3 4 3 1 3 2 4 1 4
output
3 3 2 4 2 2 1 1 3 4 3 1 4
input
5 1 2 2 4 3 4 4 5 1 2 1 3 1 4 1 5
output
4 2 1 1 2 3 4 1 3 4 2 1 4 5 4 1 5
input
9 7 9 2 8 2 1 7 5 4 7 2 4 9 6 3 9 1 8 4 8 2 9 9 5 7 6 1 3 4 6 5 3
output
8 4 2 9 2 9 7 6 7 5 7 5 9 6 9 4 6 8 2 8 4 3 9 3 5 2 1 1 8 7 4 1 3
Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class graph {
public:
struct edge {
int from;
int to;
T cost;
};
vector<edge> edges;
vector<vector<int>> g;
int n;
graph(int _n) : n(_n) {
g.resize(n);
}
virtual int add(int from, int to, T cost) = 0;
};
template <typename T>
class forest : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;
forest(int _n) : graph<T>(_n) {
}
int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
int id = (int) edges.size();
assert(id < n - 1);
g[from].push_back(id);
g[to].push_back(id);
edges.push_back({from, to, cost});
return id;
}
};
template <typename T>
class dfs_forest : public forest<T> {
public:
using forest<T>::edges;
using forest<T>::g;
using forest<T>::n;
vector<int> pv;
vector<int> pe;
vector<int> order;
vector<int> pos;
vector<int> end;
vector<int> sz;
vector<int> root;
vector<int> depth;
vector<T> dist;
dfs_forest(int _n) : forest<T>(_n) {
}
void init() {
pv = vector<int>(n, -1);
pe = vector<int>(n, -1);
order.clear();
pos = vector<int>(n, -1);
end = vector<int>(n, -1);
sz = vector<int>(n, 0);
root = vector<int>(n, -1);
depth = vector<int>(n, -1);
dist = vector<T>(n);
}
void clear() {
pv.clear();
pe.clear();
order.clear();
pos.clear();
end.clear();
sz.clear();
root.clear();
depth.clear();
dist.clear();
}
private:
void do_dfs(int v) {
pos[v] = (int) order.size();
order.push_back(v);
sz[v] = 1;
for (int id : g[v]) {
if (id == pe[v]) {
continue;
}
auto &e = edges[id];
int to = e.from ^ e.to ^ v;
depth[to] = depth[v] + 1;
dist[to] = dist[v] + e.cost;
pv[to] = v;
pe[to] = id;
root[to] = (root[v] != -1 ? root[v] : to);
do_dfs(to);
sz[v] += sz[to];
}
end[v] = (int) order.size() - 1;
}
void do_dfs_from(int v) {
depth[v] = 0;
dist[v] = T{};
root[v] = v;
pv[v] = pe[v] = -1;
do_dfs(v);
}
public:
void dfs(int v, bool clear_order = true) {
if (pv.empty()) {
init();
} else {
if (clear_order) {
order.clear();
}
}
do_dfs_from(v);
}
void dfs_all() {
init();
for (int v = 0; v < n; v++) {
if (depth[v] == -1) {
do_dfs_from(v);
}
}
assert((int) order.size() == n);
}
};
template <typename T>
class lca_forest : public dfs_forest<T> {
public:
using dfs_forest<T>::edges;
using dfs_forest<T>::g;
using dfs_forest<T>::n;
using dfs_forest<T>::pv;
using dfs_forest<T>::pos;
using dfs_forest<T>::end;
using dfs_forest<T>::depth;
int h;
vector<vector<int>> pr;
lca_forest(int _n) : dfs_forest<T>(_n) {
}
inline void build_lca() {
assert(!pv.empty());
int max_depth = 0;
for (int i = 0; i < n; i++) {
max_depth = max(max_depth, depth[i]);
}
h = 1;
while ((1 << h) <= max_depth) {
h++;
}
pr.resize(n);
for (int i = 0; i < n; i++) {
pr[i].resize(h);
pr[i][0] = pv[i];
}
for (int j = 1; j < h; j++) {
for (int i = 0; i < n; i++) {
pr[i][j] = (pr[i][j - 1] == -1 ? -1 : pr[pr[i][j - 1]][j - 1]);
}
}
}
inline bool anc(int x, int y) {
return (pos[x] <= pos[y] && end[y] <= end[x]);
}
inline int go_up(int x, int up) {
assert(!pr.empty());
up = min(up, (1 << h) - 1);
for (int j = h - 1; j >= 0; j--) {
if (up & (1 << j)) {
x = pr[x][j];
if (x == -1) {
break;
}
}
}
return x;
}
inline int lca(int x, int y) {
assert(!pr.empty());
if (anc(x, y)) {
return x;
}
if (anc(y, x)) {
return y;
}
for (int j = h - 1; j >= 0; j--) {
if (pr[x][j] != -1 && !anc(pr[x][j], y)) {
x = pr[x][j];
}
}
return pr[x][0];
}
};
template <typename T>
class hld_forest : public lca_forest<T> {
public:
using lca_forest<T>::edges;
using lca_forest<T>::g;
using lca_forest<T>::n;
using lca_forest<T>::pv;
using lca_forest<T>::sz;
using lca_forest<T>::pos;
using lca_forest<T>::order;
using lca_forest<T>::depth;
using lca_forest<T>::dfs;
using lca_forest<T>::dfs_all;
using lca_forest<T>::lca;
using lca_forest<T>::build_lca;
vector<int> head;
vector<int> visited;
hld_forest(int _n) : lca_forest<T>(_n) {
visited.resize(n);
}
void build_hld(const vector<int> &vs) {
for (int tries = 0; tries < 2; tries++) {
if (vs.empty()) {
dfs_all();
} else {
order.clear();
for (int v : vs) {
dfs(v, false);
}
assert((int) order.size() == n);
}
if (tries == 1) {
break;
}
for (int i = 0; i < n; i++) {
if (g[i].empty()) {
continue;
}
int best = -1, bid = 0;
for (int j = 0; j < (int) g[i].size(); j++) {
int id = g[i][j];
int v = edges[id].from ^ edges[id].to ^ i;
if (pv[v] != i) {
continue;
}
if (sz[v] > best) {
best = sz[v];
bid = j;
}
}
swap(g[i][0], g[i][bid]);
}
}
build_lca();
head.resize(n);
for (int i = 0; i < n; i++) {
head[i] = i;
}
for (int i = 0; i < n - 1; i++) {
int x = order[i];
int y = order[i + 1];
if (pv[y] == x) {
head[y] = head[x];
}
}
}
void build_hld(int v) {
build_hld(vector<int>(1, v));
}
void build_hld_all() {
build_hld(vector<int>());
}
bool apply_on_path(int x, int y, bool with_lca, function<void(int,int,bool)> f) {
// f(x, y, up): up -- whether this part of the path goes up
assert(!head.empty());
int z = lca(x, y);
if (z == -1) {
return false;
}
{
int v = x;
while (v != z) {
if (depth[head[v]] <= depth[z]) {
f(pos[z] + 1, pos[v], true);
break;
}
f(pos[head[v]], pos[v], true);
v = pv[head[v]];
}
}
if (with_lca) {
f(pos[z], pos[z], false);
}
{
int v = y;
int cnt_visited = 0;
while (v != z) {
if (depth[head[v]] <= depth[z]) {
f(pos[z] + 1, pos[v], false);
break;
}
visited[cnt_visited++] = v;
v = pv[head[v]];
}
for (int at = cnt_visited - 1; at >= 0; at--) {
v = visited[at];
f(pos[head[v]], pos[v], false);
}
}
return true;
}
};
template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
void modify(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
hld_forest<int> g(n);
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
--x; --y;
g.add(x, y);
}
dfs_forest<int> f(n);
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
--x; --y;
f.add(x, y);
}
g.build_hld(0);
f.dfs(0);
cout << n - 1 << '\n';
fenwick<int> fenw(n);
for (int i = 1; i < n; i++) {
fenw.modify(i, 1);
}
for (int it = n - 1; it >= 1; it--) {
int x = f.order[it];
int y = f.pv[x];
bool found = false;
g.apply_on_path(x, y, false, [&](int from, int to, bool up) {
if (found) {
return;
}
int sum = fenw.get(to) - fenw.get(from - 1);
if (sum > 0) {
found = true;
if (up) {
int low = from, high = to;
while (low < high) {
int mid = (low + high + 1) >> 1;
sum = fenw.get(to) - fenw.get(mid - 1);
if (sum > 0) {
low = mid;
} else {
high = mid - 1;
}
}
fenw.modify(low, -1);
int v = g.order[low];
cout << v + 1 << " " << g.pv[v] + 1 << " " << x + 1 << " " << y + 1 << '\n';
} else {
int low = from, high = to;
while (low < high) {
int mid = (low + high) >> 1;
sum = fenw.get(mid) - fenw.get(from - 1);
if (sum > 0) {
high = mid;
} else {
low = mid + 1;
}
}
fenw.modify(low, -1);
int v = g.order[low];
cout << v + 1 << " " << g.pv[v] + 1 << " " << x + 1 << " " << y + 1 << '\n';
}
}
});
assert(found);
}
return 0;
}
