1. 题目

传送门=￣ω￣=

题目描述

有一个 $N$个节点的树，节点从 $1$到 $n$标号，$N−1$条边中的第 $i$条边连接节点 $a _ i$和 $b _ i$。

开始的时候所有的边都是蓝色，$Takahashi$会通过 $n−1$步操作把这个蓝色的树变成红色。

每次操作包含以下步骤：

$1$. 选择一个只包含蓝色的简单路径，然后移除上面的一条边。

$2$. 在选出的蓝色简单路径的两个端点之间加一条红边。

他想把树变恰好变成一棵每条边连接 $c _ i$, $d _ i$的红色的树。

请问他能否达成他的目标？

输入格式

以以下格式从标准输入读入

$N$
$a _ 1 b _ 1$

…

$a _ {N−1} b _ {N−1}$

$c _ 1 d _ 1$
..

$c _ {N−1} d _ {N−1}$

输出格式

如果可以达成，输出’YES’，否则输出’NO’。

样例

样例输入 1

3
1 2
2 3
1 3
3 2

样例输出 1

YES

样例解释 1

目标可以达成，至少： 1. 选择连接节点 1 和 3 的路径，然后移除蓝边 1−2，加入红边 1−3。 2. 选择连接节点 2 和 3 的路径，然后移除蓝边 2−3，加入红边 2−3

样例输入 2

5
1 2
2 3
3 4
4 5
3 4
2 4
1 4
1 5

样例输出 2

YES

样例输入 3

6
1 2
3 5
4 6
1 6
5 1
5 3
1 4
2 6
4 3
5 6

样例输出 3

NO

2. 题解

时光倒流好妙啊

考虑最后时刻，一条同时存在于两棵树上的边 $u -> v$

显然是直接从蓝树上切除 $u -> v$，再在红树上添加 $u -> v$。

然后假如蓝树上有一条 $v -> w$，红树上有一条 $u -> w$

那么其实蓝树就是通过切除 $u -> w$路径上的 $v -> w$从而在红树上添加 $u -> w$，然后再在蓝树上切除 $u -> v$从而在红树上添加 $u -> v$。

那么我们就是每次找到一条出现了两次的边，然后将它的俩端点合并为一个点，连向它们的边也都合并到那个点上。

这时候就有可能多出一些出现次数等于二的边，把它们加到队列里挨个处理即可。

最后合并完所有的边后如果剩下的点的个数等于 1 则说明有可行方案，否则说明没有。

具体实现就是用 $n$个 set 维护每个点的出边，方便删边。

然后用 map<pair<int, int>, int> 维护每条边出现了多少次。

再搞个并查集维护合并以后的点，合并的时候启发式合并一下即可。

复杂度 $O(n log _ 2 ^ 2 n)$

代码：

#include <bits/stdc++.h>

#define NS (100005)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, fa[NS];

map<PII, int> mp;

set<int> g[NS];

queue<PII> que;

int findf(int a) {return fa[a] == a ? a : fa[a] = findf(fa[a]);}

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1; i <= n; i += 1) fa[i] = i;
    for (int i = 1, a, b; i < n; i += 1)
    {
        IN(a), IN(b);
        if (a > b) swap(a, b);
        mp[PII(a, b)]++;
        g[a].insert(b), g[b].insert(a);
    }
    for (int i = 1, a, b; i < n; i += 1)
    {
        IN(a), IN(b);
        if (a > b) swap(a, b);
        if (++mp[PII(a, b)] == 2) que.push(PII(a, b));
        g[a].insert(b), g[b].insert(a);
    }
    int cnt = 0;
    while (!que.empty())
    {
        int u = findf(que.front().FIR), v = findf(que.front().SEC); que.pop();
        if (g[u].size() > g[v].size()) swap(u, v);
        for (set<int>::iterator i = g[u].begin(); i != g[u].end(); i++)
            if (*i != v)
            {
                g[*i].erase(u), g[*i].insert(v), g[v].insert(*i);
                int a = *i, b = v;
                if (a > b) swap(a, b);
                if (++mp[PII(a, b)] == 2) que.push(PII(a, b));
            }
        g[v].erase(u), fa[u] = v, cnt++;
    }
    if (cnt == n - 1) puts("YES");
    else puts("NO");
    return 0;
}