Language: C++

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

vector<int> nullvi;
set<int> nullsi;

queue<int> que;
bool used[100010];

struct seg{
	int siz;
	vector<set<int>> s;
	vector<P> t;
	vector<int> u;
	void init(int n){
		siz = 1;
		while(siz < n)siz <<= 1;
		rep(i,siz*2-1){
			s.push_back(nullsi);
			t.push_back(P(0,0));
			u.push_back(0);
		}
		rep(i,siz){
			t[i+siz-1] = P(0,i);
		}
		rrep(i,siz-1){
			t[i] = min( t[2*i+1] , t[2*i+2] );
		}
	}
	void add(int a,int b,int x,int k,int l,int r){
		//fprintf(stderr,"seg:add(%d,%d,%d,%d,%d,%d)\n",a,b,x,k,l,r);
		if(b <= l || r <= a)return;
		if(a <= l && r <= b){
			//if(x != -1){
				s[k].insert(x);
				u[k] ++;
				t[k].fr += 1;
			/*}
			else {
				u[k] += INF;
				t[k].fr += INF;
			}*/
			return;
		}
		add(a,b,x,2*k+1,l,(l+r)/2);
		add(a,b,x,2*k+2,(l+r)/2,r);
		t[k] = min( t[2*k+1] , t[2*k+2] );
		t[k].fr += u[k];
	}
	void erase(int a,int b,int x,int k,int l,int r){
		if(b <= l || r <= a)return;
		if(a <= l && r <= b){
			s[k].erase(x);
			u[k] --;
			t[k].fr -= 1;
			return;
		}
		erase(a,b,x,2*k+1,l,(l+r)/2);
		erase(a,b,x,2*k+2,(l+r)/2,r);
		t[k] = min( t[2*k+1] , t[2*k+2] );
		t[k].fr += u[k];
	}
	void query(int a,int b,int cnt,int k,int l,int r){
		//fprintf(stderr,"seg:query(%d,%d,%d,%d,%d,%d)\n",a,b,cnt,k,l,r);
		if(b <= l || r <= a)return;
		if(t[k].fr+cnt >= 2)return;
		if(s[k].size() == 1){
			que.push(*s[k].begin());
			cnt ++;
		}
		if(r-l == 1){
			u[k] += INF;
			t[k].fr += INF;
			return;
		}
		query(a,b,cnt,2*k+1,l,(l+r)/2);
		query(a,b,cnt,2*k+2,(l+r)/2,r);
		t[k] = min( t[2*k+1] , t[2*k+2] );
		t[k].fr += u[k];
	}
	/*int cnt(int a){
		a += siz-1;
		int ret = u[a];
		while(a > 0){
			a = (a-1)/2;
			ret += u[a];
		}
		return ret;
	}*/
	/*P _query(int a,int b,int k,int l,int r){
		if(b <= l || r <= a)return P(INF,INF);
		if(a <= l && r <= b)return t[k];
		P chl = _query(a,b,2*k+1,l,(l+r)/2);
		P chr = _query(a,b,2*k+2,(l+r)/2,r);
		P ret = min(chl,chr);
		ret.fr += u[k];
		return ret;
	}
	int query(int a,int b){
		P p = _query(a,b,0,0,siz);
		if(p.fr != 1)return -1;
		int loc = p.sc+siz-1;
		while(1){
			if(s[loc].size() > 0)return *s[loc].begin();
			loc = (loc-1)/2;
		}
		return -1;
	}
	int cnt(int a){
		a += siz-1;
		int ret = u[a];
		while(a > 0){
			a = (a-1)/2;
			ret += u[a];
		}
		return ret;
	}*/
};

struct UF{
	vector<int> par,r;
	void init(int n){
		rep(i,n+1){
			par.pb(i);
			r.pb(0);
		}
	}
	int find(int x){
		if(par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	bool same(int x,int y){
		return find(x) == find(y);
	}
	void unit(int x,int y){
		if(same(x,y))return;
		x = find(x);
		y = find(y);
		if(r[x] < r[y]){
			par[x] = y;
		}
		else {
			par[y] = x;
			if(r[x] == r[y]){
				r[x] ++;
			}
		}
	}
};

struct HL{
	int V;
	vector<vector<int>> G;
	int x,y;
	vector<int> d[2];
	int D;
	vector<int> id;
	vector<P> loc;
	UF uf;
	vector<HL*> ch;
	vector<vector<int>> ch_ids;
	vector<int> root;
	void init(int _V){
		V = _V;
		rep(i,V+1){
			G.push_back(nullvi);
			d[0].push_back(-1);
			d[1].push_back(-1);
			loc.push_back(P(-1,-1));
		}
		//G = vector<vector<int>>(V+1);
	}
	void add_edge(int a,int b){
		G[a].pb(b); G[b].pb(a);
	}
	void dfs(int v,int p,int t){
		d[t][v] = d[t][p]+1;
		for(int u: G[v]){
			if(u == p)continue;
			dfs(u,v,t);
		}
	}
	void dia(){
		x = 1;
		d[0][0] = -1;
		dfs(x,0,0);
		rep1(i,V)if(d[0][i]>d[0][x])x=i;
		d[1][0] = -1;
		dfs(x,0,0);
		y = 1;
		rep1(i,V)if(d[0][i]>d[0][y])y=i;
		dfs(y,0,1);
	}
	void run_HL(){
		/*cerr << "==========" << endl;
		cerr << V << endl;
		rep1(i,V){
			for(int j: G[i]){
				cerr << i << " " << j << endl;
			}
		}*/
	//cerr << __LINE__ << endl;
		dia();
	//cerr << __LINE__ << endl;
		D = d[0][y];
		rep(i,D+1){
			id.push_back(-1);
		}
	//cerr << __LINE__ << endl;
		rep1(i,V){
			if(d[0][i]+d[1][i] == D){
				id[d[0][i]] = i;
				loc[i] = P(-1,d[0][i]);
			}
			else loc[i] = P(-2,0);
		}
	//cerr << __LINE__ << endl;
		uf.init(V);
		rep1(i,V){
			if(loc[i].fr != -2)continue;
			for(int j: G[i]){
				if(loc[j].fr == -2)uf.unit(i,j);
			}
		}
	//cerr << __LINE__ << endl;
		rep1(i,V){
			if(loc[i].fr == -1)continue;
			if(loc[uf.find(i)].fr == -2){
				loc[uf.find(i)].fr = ch_ids.size();
				ch.push_back(new HL);
				ch_ids.push_back(nullvi);
				root.push_back(0);
				ch_ids[loc[uf.find(i)].fr].push_back(uf.find(i));
				loc[uf.find(i)].sc = 1;
			}
			if(uf.find(i) != i){
				loc[i].fr = loc[uf.find(i)].fr;
				ch_ids[loc[i].fr].push_back(i);
				loc[i].sc = ch_ids[loc[i].fr].size();
			}
		}
	//cerr << __LINE__ << endl;
		rep(i,ch_ids.size()){
	//cerr << __LINE__ << endl;
			ch[i]->init(ch_ids[i].size()+1);
			int _v = ch_ids[i][0];
			root[i] = id[d[0][_v]-(d[0][_v]+d[1][_v]-D)/2];
	//cerr << __LINE__ << endl;
			for(int v: ch_ids[i]){
				for(int u: G[v]){
					if(u == root[i])ch[i]->add_edge(loc[v].sc,ch_ids[i].size()+1);
					else if(loc[v].sc < loc[u].sc)ch[i]->add_edge(loc[v].sc,loc[u].sc);
				}
			}
	//cerr << __LINE__ << endl;
			ch_ids[i].pb(root[i]);
	//cerr << __LINE__ << endl;
			ch[i]->run_HL();
	//cerr << __LINE__ << endl;
		}
	//cerr << __LINE__ << endl;
		init_adhoc();
	//cerr << __LINE__ << endl;
	}
	seg seg;
	void init_adhoc(){
		seg.init(id.size());
	}
	void add(int a,int b,int c){
		if(loc[a] > loc[b])swap(a,b);
		if(loc[b].fr == -1){
			seg.add(loc[a].sc,loc[b].sc,c,0,0,seg.siz);
		}
		else if(loc[a].fr == -1){
			if(loc[a].sc <= loc[root[loc[b].fr]].sc)seg.add(loc[a].sc,loc[root[loc[b].fr]].sc,c,0,0,seg.siz);
			else seg.add(loc[root[loc[b].fr]].sc,loc[a].sc,c,0,0,seg.siz);
			ch[loc[b].fr]->add(loc[root[loc[b].fr]].sc,loc[b].sc,c);
		}
		else {
			if(loc[root[loc[a].fr]].sc>loc[root[loc[b].fr]].sc)swap(a,b);
			seg.add(loc[root[loc[a].fr]].sc,loc[root[loc[b].fr]].sc,c,0,0,seg.siz);
			ch[loc[a].fr]->add(loc[root[loc[a].fr]].sc,loc[a].sc,c);
			ch[loc[b].fr]->add(loc[root[loc[b].fr]].sc,loc[b].sc,c);
		}
	}
	void erase(int a,int b,int c){
		if(loc[a] > loc[b])swap(a,b);
		if(loc[b].fr == -1){
			seg.erase(loc[a].sc,loc[b].sc,c,0,0,seg.siz);
		}
		else if(loc[a].fr == -1){
			if(loc[a].sc <= loc[root[loc[b].fr]].sc)seg.erase(loc[a].sc,loc[root[loc[b].fr]].sc,c,0,0,seg.siz);
			else seg.erase(loc[root[loc[b].fr]].sc,loc[a].sc,c,0,0,seg.siz);
			ch[loc[b].fr]->erase(loc[root[loc[b].fr]].sc,loc[b].sc,c);
		}
		else {
			if(loc[root[loc[a].fr]].sc>loc[root[loc[b].fr]].sc)swap(a,b);
			seg.erase(loc[root[loc[a].fr]].sc,loc[root[loc[b].fr]].sc,c,0,0,seg.siz);
			ch[loc[a].fr]->erase(loc[root[loc[a].fr]].sc,loc[a].sc,c);
			ch[loc[b].fr]->erase(loc[root[loc[b].fr]].sc,loc[b].sc,c);
		}
	}
	void query(int a,int b){
		//cerr << __LINE__ << endl;
		//fprintf(stderr,"HL::query(%d,%d)\n",a,b);
		if(loc[a] > loc[b])swap(a,b);
		if(loc[b].fr == -1){
		//cerr << __LINE__ << endl;
			seg.query(loc[a].sc,loc[b].sc,0,0,0,seg.siz);
		}
		else if(loc[a].fr == -1){
		//cerr << __LINE__ << endl;
			if(loc[a].sc <= loc[root[loc[b].fr]].sc)seg.query(loc[a].sc,loc[root[loc[b].fr]].sc,0,0,0,seg.siz);
			else seg.query(loc[root[loc[b].fr]].sc,loc[a].sc,0,0,0,seg.siz);
			ch[loc[b].fr]->query(loc[root[loc[b].fr]].sc,loc[b].sc);
		}
		else {
		//cerr << __LINE__ << endl;
			if(loc[root[loc[a].fr]].sc>loc[root[loc[b].fr]].sc)swap(a,b);
			seg.query(loc[root[loc[a].fr]].sc,loc[root[loc[b].fr]].sc,0,0,0,seg.siz);
			ch[loc[a].fr]->query(loc[root[loc[a].fr]].sc,loc[a].sc);
			ch[loc[b].fr]->query(loc[root[loc[b].fr]].sc,loc[b].sc);
		}
	}
	/*int cnt(int a){
		if(loc[a].fr == -1)return seg.cnt(loc[a].sc);
		return ch[loc[a].fr]->cnt(loc[a].sc);
	}*/
	/*void out(){
		cerr << "diameter:";
		for(int v: id)cerr << v << " ";
		cerr << endl;
		rep1(i,V){
			cerr << i << ":" << loc[i].fr << " " << loc[i].sc << endl;
		}
		rep(i,ch.size()){
			cerr << "=========ch[" << i << "]==========" << endl;
			cerr << "par=" << par[i] << ",root=" << root[i] << endl;
			ch[i]->out();
		}
	}*/
};

int main(){
	static int n;
	static int a[100010],b[100010];
	static int c[100010],d[100010];
	scanf("%d",&n);
	rep1(i,n-1)scanf("%d%d",&a[i],&b[i]);
	rep1(i,n-1)scanf("%d%d",&c[i],&d[i]);
	
	//cerr << __LINE__ << endl;
	static HL* tree = new HL;
	tree->init(n);
	//cerr << __LINE__ << endl;
	rep1(i,n-1){
		tree->add_edge(a[i],b[i]);
	}
	//cerr << __LINE__ << endl;
	tree->run_HL();
	
	//cerr << __LINE__ << endl;
	rep1(i,n-1){
		tree->add(c[i],d[i],i);
	}
	//cerr << __LINE__ << endl;
	rep1(i,n){
		tree->query(a[i],b[i]);
		used[i] = false;
	}
	//cerr << __LINE__ << endl;
	
	//cout << que.size() << endl;
	
	int cnt = 0;
	while(!que.empty()){
		int p = que.front(); que.pop();
		//cout << p << endl;
		if(used[p])continue;
		used[p] = true; cnt ++;
		tree->erase(c[p],d[p],p);
		tree->query(c[p],d[p]);
	}
	if(cnt == n-1)puts("YES");
	else puts("NO");
	//tree->out();
}


Compiler output:
a.cc:298:13: error: declaration of 'seg HL::seg' changes meaning of 'seg' [-Wchanges-meaning]
  298 |         seg seg;
      |             ^~~
a.cc:298:9: note: used here to mean 'struct seg'
  298 |         seg seg;
      |         ^~~
a.cc:43:8: note: declared here
   43 | struct seg{
      |        ^~~