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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

boshi · 2018年10月12日 3:58 下午

nlogn可以秒天秒地

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *