Noip 2019合宿テスト試合(二十一)Problem B:赤と青の木

Noip 2019合宿テスト試合(二十一)Problem B:赤と青の木

Description

一本ある
N個の点、頂点番号が1からNの木.N−1辺のi番目の辺は頂点aiとbiを接続する.各エッジは、最初に青に染められます.高橋君はN−1回操作して、この青い木を赤い木に変えます.*青いエッジのみを含む単純なパスを選択し、これらのエッジの1つを削除します.*次に、パスの2つの端点の間に赤いエッジが接続されます.彼の目標は、iごとにciとdiを接続する赤いエッジがあることです.今、彼の目標を達成できるかどうかを判断してください.

Input

タイトルデータは下記の形式で標準入出力から入力します.
NNa1 b1⋮aN−1 bN−1c1 d1⋮cN−1 dN−1

Output

もし目標が達成できるならば、出力`YES`を出して、さもなくば出力`NO`を出します.

Sample Input

sample input 1:
3
1 2
2 3
1 3
3 2
sample input 2:
5
1 2
2 3
3 4
4 5
3 4
2 4
1 4
1 5
sample input 3:
6
1 2
3 5
4 6
1 6
5 1
5 3
1 4
2 6
4 3
5 6

Sample Output

sample output 1:
YES
sample output 2:
YES
sample output 3:
NO

HINT

サンプル1:目標達成可能:
*まず、頂点の接続を選択します.
1～33のエッジを削除し、1～2の間の青いエッジを除去し、1～3の間に赤いエッジを生成します.*次に、頂点2と3を接続するエッジを選択し、2と3の間の青いエッジを削除し、2と3の間に赤いエッジを生成します.
*2≦N≦105*1≦ai,bi,ci,di≦N*ai≠bi*ci≠di*入力の2つの図はツリーです.

解析:

赤い木を青い木に変えることができれば、N-2のエッジを変えた後、最後の青いエッジが最後の赤いエッジと重なることはありません.
この重なり合うエッジは、以前のすべてのエッジで任意に使用できます.
では、元のツリーのそれぞれの赤で青のエッジの2つの端点を1つの点に縮めることができます(元の接続されたエッジを削除し、1つの点のすべてのエッジを別の点に移動し、啓発的に結合して点を縮めることができます).
最終的に木全体を一つの点に縮めることができれば、YESであり、そうでなければNOである.
イニシアチブマージの総消費時間はO(nlogn)
アルゴリズム全体の時間的複雑さはO(nlogn)である.

#include
#include
#include<set>
using namespace std;
struct data{
    int x,y;
}t[200001];
int n,m,f[200001],x,y,cnt;
set<int> v[200001];
int fa(int a){
    if(f[a]!=a)f[a]=fa(f[a]);
    return f[a];
}
void ins(int a,int b){
    set<int>::iterator id1=v[a].find(b),id2=v[b].find(a);
    if(id1==v[a].end()){
        v[a].insert(b);
        v[b].insert(a);
    }else{
        cnt++;
        v[a].erase(b);
        v[b].erase(a);
        t[cnt].x=a;
        t[cnt].y=b;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n*2-2;i++){
        scanf("%d%d",&x,&y);
        ins(x,y);
    }
    for(int i=1;i<=n;i++)f[i]=i;
    while(cnt){
        x=fa(t[cnt].x);
        y=fa(t[cnt].y);
        cnt--;
        if(v[x].size()>v[y].size())swap(x,y);
        f[x]=y;
        for(int i:v[x]){
            v[i].erase(x);
            ins(i,y);
        }
        v[x].clear();
        m++;
    }
    if(m==n-1)printf("YES
");
    else printf("NO
");
}