Language: C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
struct uf{
	int par[100005],ran[100005];
	void init(){
		for(int i=0;i<100005;i++){
			par[i] = i;
			ran[i] = 0;
		}
	}
	int find(int x){
		if(x == par[x]) return x;
		else return par[x] = find(par[x]);
	}
	void unite(int x,int y){
		x = find(x); y = find(y);
		if(x == y) return;
		if(ran[x] < ran[y]) par[x] = y;
		else{
			par[y] = x;
			if(ran[x] == ran[y]) ran[x]++;
		}
	}
}U;
bool up[100005],col[100005];
int p[100005],num[100005],dw[100005],dep[100005],db[100005][18];
int S[100005];
vector<int>edge[100005],edge2[100005];
int val[100005];
int ty[100005],pos[100005],L[100005],N[100005],W[100005],C=1;
int dfs(int v,int u){
	int vs=-1,vi=-1; N[v]=C++;
	int sz=1;
	if(u == -1) dep[v] = 1;
	else dep[v] = dep[u]+1;
	db[v][0] = u;
	for(int i=0;i<edge[v].size();i++){
		if(edge[v][i] == u) continue;
		int x = dfs(edge[v][i],v);
		if(x > vs){
			vs = x; vi = edge[v][i];
		}
		sz += x;
	}
	up[vi] = 1;
	dw[v] = vi;W[v] = C-1;
	return sz;
}
void dfs2(int v,int u){
	for(int i=0;i<edge[v].size();i++){
		if(edge[v][i] == u) continue;
		dfs2(edge[v][i],v);
		val[v] += val[edge[v][i]];
	}
}
void make(int v,int u,int ko){
	if(ko == 1) p[v] = v;
	else p[v] = p[u];
	S[p[v]] = ko;
	num[v] = ko; bool U = 0;
	for(int i=0;i<edge[v].size();i++){
		if(edge[v][i] == u) continue;
		if(dw[v] == edge[v][i]) {make(edge[v][i],v,ko+1);U=1;}
		else make(edge[v][i],v,1);
	}
	if(!U) L[v] = p[v];
}
int lca(int u,int v){
	if(dep[u] > dep[v]) swap(u,v);
	for(int i=0;i<18;i++){
		if((((dep[v]-dep[u])>>i)&1)){
			v = db[v][i];
		}
	}
	assert(dep[u] == dep[v]);
	if(u == v) return u;
	for(int i=17;i>=0;i--){
		if(db[u][i] != db[v][i]){
			u = db[u][i];
			v = db[v][i];
		}
	}
	return db[u][0];
}
struct hl{
	int s;
	vector<int>seg,f,mem;
	void update(vector<int>hoge){
		mem = hoge;
	}
	void make(int x){
		for(int i=0;i<18;i++){
			if(x < (1<<i)){
				s = (1<<i);
				seg.resize(s*2,INF);
				f.resize(s*2,0);
				break;
			}
		}
	}
	void lazy(int k,int l,int r){
		f[k*2+1] = f[k];
		f[k*2+2] = f[k];
		seg[k*2+1]-=f[k];
		seg[k*2+2]-=f[k];
		f[k] = 0;
	}
	void upd(int a,int b,int k,int l,int r,int a){
		k+=s-1;
		seg[k] = min(seg[k],a);
		while(k){
			k=(k-1)/2;
			seg[k]=min(seg[k*2+1],seg[k*2+2]);
		}
	}
	int add(int a,int b,int k,int l,int r,int num){
		if(r<a||b<l)return seg[k];
		if(a<=l&&r<=b){
			f[k]+=num;
			seg[k]-=num;
			return seg[k];
		}
		if(f[k]) lazy(k,l,r);
		return seg[k] = min(add(a,b,k*2+1,l,(l+r)/2,num),add(a,b,k*2+2,(l+r)/2+1,r,num));
	}
	
	int query(int a,int b,int k,int l,int r){
		if(r<a||b<l) return INF;
		if(a<=l && r<=b) return seg[k];
		if(f[k]) lazy(k,l,r);
		return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2+1,r));
	}
	int go(int k,int l,int r){
		if(l==r)return l;
		if(f[k]) lazy(k,l,r);
		if(seg[k*2+1] == 1) return go(k*2+1,l,(l+r)/2);
		else return go(k*2+2,(l+r)/2+1,r);
	}
	void find(){
		while(query(0,s-1,0,0,s-1) == 1){
			pt_erase(go(0,0,s-1));
		}
	}
	void add(int a,int b,int v){
		add(a,b,0,0,s-1,v);
	}
	int query(int a,int b){
		return query(a,b,0,0,s-1);
	}
}dat[100005];
void make2(int cur){
	int EN = L[cur]; vector<int>vi; 
	while(1){
		ty[cur] = EN; vi.pb(cur);
		if(cur == EN) break;
		else cur = db[cur][0];
	}
	vi.pb(-1); reverse(vi.begin(),vi.end());
	dat[EN].update(vi); dat[EN].make();
	for(int i=1;i<vi.size();i++){
		dat[EN].add(i,i,val[vi[i]]);
	}
}
queue<int>Q;
void go(int cur,int en){
	if(cur == en) return;
	if(!up[cur]){
		val[cur]--; if(val[cur] == 1) Q.push(cur);
		go(db[cur][0],en);
		return;
	}
	else{
		int x = num[cur];
		int P = p[cur];
		if(dep[P]>=dep[en]){
			dat[P].add(1,x-1,-1);
			dat[P].find();
			cur = p[cur];
			go(cur,en);
			return;
		}
		else{
			dat[P].upd(1+dep[en]-dep[P],x-1,-1);
			dat[P].find();
			return;
		}
	}
}
multiset<P>SS[(1<<18)];
void update3(int a,int b,int c){
	a+=(1<<17)-1; SS[a].insert(mp(b,c));
	while(a>0){
		a=(a-1)/2;
		SS[a].insert(mp(b,c));
	}
}
int find3(int a,int b,int k,int l,int r,int num){
	if(r<a||b<l) return -1;
	if(a<=l&&r<=b){
		multiset<int>::iterator it = SS[k].upper_bound(mp(num,INF));
		if(it != SS[k].begin()){
			it--; if((*it).fi>=L) return (*it).sc;else return -1;
		}
		return -1;
	}
	return max(find3(a,b,k*2+1,l,(l+r)/2,num),find3(a,b,k*2+2,(l+r)/2+1,r,num));
}
int find34(int a,int b,int k,int l,int r,int num){
	if(r<a||b<l) return -1;
	if(a<=l&&r<=b){
		multiset<int>::iterator it = SS[k].upper_bound(mp(num,-1));
		if(it != SS[k].end()){
			if((*it).fi>R) return (*it).sc; else return -1;
		}
		return -1;
	}
	return max(find34(a,b,k*2+1,l,(l+r)/2,num),find34(a,b,k*2+2,(l+r)/2+1,r,num));
}
bool bad = 0;
P p[100005]; int xxxx = 0;
void pt_erase(int nu){
	int A = ty[nu],B = num[nu];xxxx++;
	int x = dat[A].query(B,B,0,0,s-1);
	if(x != 1){
		bad = 1; return;
	}
	dat[A].add(B,B,INF);
	int L = N[nu],R = W[nu];
	int WW = find3(0,L-1,0,0,(1<<17)-1,R);
	int WW2 = find4(L,R,0,0,(1<<17)-1,R);
	WW=max(WW,WW2);
	int vv = lca(p[WW].fi,p[WW].sc);
	go(p[WW].fi,vv);
	go(p[WW].sc,vv);
}

int main(){
	cin>>n; U.init();
	rep(i,n-1){
		int a,b;scanf("%d%d",&a,&b);edge[a].pb(b);edge[b].pb(a);
	}
	rep(i,n-1){
		int a,b;scanf("%d%d",&a,&b);edge2[a].pb(b);edge2[b].pb(a);
	}
	dfs(1,-1);
	make(1,-1,1);
	for(int j=0;j<17;j++){
		for(int i=1;i<=n;i++){
			if(db[i][j] == -1){
				db[i][j+1] = -1;
			}
			else{
				db[i][j+1] = db[db[i][j]][j];
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<edge[i].size();j++){
			if(i<edge[i][j]) continue;
			val[i]++; val[edge[i][j]]++; val[lca(i,edge[i][j])]-=2;
		}
	}
	dfs2(1,-1); int F=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<edge2[i].size();j++){
			if(i<edge2[i][j]) continue;
			int x = N[i],y = N[edge2[i][j]];
			if(x>y) swap(x,y);
			update3(x,y,F); p[F]=mp(edge2[i][j],i); F++;
		}
	}
	for(int i=1;i<=n;i++){
		if(L[i]) make2(i);
	}
	for(int i=2;i<=n;i++){
		if(val[i] == 1){
			pt_erase(i); while(Q.size()){ pt_erase(Q.front()); Q.pop(); }
		}
	}
	while(Q.size()){pt_erase(Q.front()); Q.pop(); }
	puts(!bad&&xxxx==n?"YES":"NO");
}

Compiler output:
a.cc:126:52: error: redefinition of 'int a'
  126 |         void upd(int a,int b,int k,int l,int r,int a){
      |                                                ~~~~^
a.cc:126:22: note: 'int a' previously declared here
  126 |         void upd(int a,int b,int k,int l,int r,int a){
      |                  ~~~~^
a.cc: In member function 'void hl::find()':
a.cc:159:25: error: 'pt_erase' was not declared in this scope
  159 |                         pt_erase(go(0,0,s-1));
      |                         ^~~~~~~~
a.cc: In function 'void make2(int)':
a.cc:177:41: error: no matching function for call to 'hl::make()'
  177 |         dat[EN].update(vi); dat[EN].make();
      |                             ~~~~~~~~~~~~^~
a.cc:109:14: note: candidate: 'void hl::make(int)'
  109 |         void make(int x){
      |              ^~~~
a.cc:109:14: note:   candidate expects 1 argument, 0 provided
a.cc: In function 'int find3(int, int, int, int, int, int)':
a.cc:218:63: error: conversion from '_Rb_tree_const_iterator<std::pair<int, int>>' to non-scalar type '_Rb_tree_const_iterator<int>' requested
  218 |                 multiset<int>::iterator it = SS[k].upper_bound(mp(num,INF));
      |                                              ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
a.cc:219:23: error: no match for 'operator!=' (operand types are 'std::multiset<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} and 'std::multiset<std::pair<int, int> >::iterator' {aka 'std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator'})
  219 |                 if(it != SS[k].begin()){
      |                    ~~ ^~ ~~~~~~~~~~~~~
      |                    |                |
      |                    |                _Rb_tree_const_iterator<std::pair<int, int>>
      |                    _Rb_tree_const_iterator<int>
In file included from /usr/include/c++/14/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:181,
                 from a.cc:1:
/usr/include/c++/14/bits/regex.h:1132:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, const sub_match<_BiIter>&)'
 1132 |     operator!=(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1132:5: note:   template argument deduction/substitution failed:
a.cc:219:38: note:   'std::multiset<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  219 |                 if(it != SS[k].begin()){
      |                                      ^
/usr/include/c++/14/bits/regex.h:1212:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const sub_match<_BiIter>&)'
 1212 |     operator!=(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1212:5: note:   template argument deduction/substitution failed:
a.cc:219:38: note:   'std::multiset<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
  219 |                 if(it != SS[k].begin()){
      |                                      ^
/usr/include/c++/14/bits/regex.h:1305:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1305 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1305:5: note:   template argument deduction/substitution failed:
a.cc:219:38: note:   'std::multiset<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  219 |                 if(it != SS[k].begin()){
      |                                      ^
/usr/include/c++/14/bits/regex.h:1379:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type*, const sub_match<_BiIter>&)'
 1379 |     operator!=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1379:5: note:   template argument deduction/substitution failed:
a.cc:219:38: note:   'std::multiset<std::pair<int, int> >::iterator' {aka 'std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  219 |                 if(it != SS[k].begin()){
      |                                      ^
/usr/include/c++/14/bits/regex.h:1473:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1473 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1473:5: note:   template argument deduction/substitution failed:
a.cc:219:38: note:   'std::multiset<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  219 |                 if(it != SS[k].begin()){
      |                                      ^
/usr/include/c++/14/bits/regex.h:1547:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type&, const sub_match<_BiIter>&)'
 1547 |     operator!=(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1547:5: note:   template argument deduction/substitution failed:
a.cc:219:38: note:   'std::multiset<std::pair<int, int> >::iterator' {aka 'std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  219 |                 if(it != SS[k].begin()){
      |                                      ^
/usr/include/c++/14/bits/regex.h:1647:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1647 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1647:5: note:   template argument deduction/substitution failed:
a.cc:219:38: note:   'std::multiset<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  219 |                 if(it != SS[k].begin()){
      |                                      ^
/usr/include/c++/14/bits/regex.h:2213:5: note: candidate: 'template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator!=(const match_results<_BiIter, _Alloc>&, const match_results<_BiIter, _Alloc>&)'
 2213 |     operator!=(const match_results<_Bi_iter, _Alloc>& __m1,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:2213:5: note:   template argument deduction/substitution failed:
a.cc:219:38: note:   'std::multiset<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
  219 |                 if(it != SS[k].begin()){
      |                                      ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:1052:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator!=(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1052 |     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1052:5: note:   template argument deduction/substitution failed:
a.cc:219:38: note:   'std::multiset<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} is not derived from 'const std::pair<_T1, _T2>'
  219 |                 if(it != SS[k].begin()){
      |                                      ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:455:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator!=(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  455 |     operator!=(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:455:5: note:   template argument deduction/substitution failed:
a.cc:219:38: note:   'std::multiset<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} is not derived from 'const std::reverse_iterator<_Iterator>'
  219 |                 if(it != SS[k].begin()){
      |                                      ^
/usr/include/c++/14/bits/stl_iterator.h:500:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator!=(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  500 |     operator!=(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:500:5: note:   template argument deduction/substitution failed:
a.cc:219:38: note:   'std::multiset<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>,