【学习笔记】优化建图相关（线段树优化，倍增优化）

• 前言
• 线段树优化建图
  • 单点连区间
  • 区间连区间
  • 例题
    • 解题：
• 倍增优化建图
  • 例题
    • 解题：

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
#define next Miku
typedef long double llf;
typedef long long ll;
typedef pair<int,int> PII;
const double eps=1e-8;
namespace io{
//	char in[1<<20],*p1=in,*p2=in;
//	#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
	il int read(){
   		char c=getchar();
    	int x=0,f=1;
   		while(c<48)<%if(c=='-')f=-1;c=getchar();%>
    	while(c>47)x=(x*10)+(c^48),c=getchar();
    	return x*f;
	}
	il void write(int x){
    	if(x<0)<%putchar('-');x=~x+1;%>
    	if(x>9) write(x/10);
   		putchar(x%10+'0');
	} 
	il int ins(char *str){
		int len=0;
		while(1){
			char c=getchar();
			if(c!='\n' && c!='\0' && c!='\r')	str[++len]=c;
			else	break;
		}
		return len;
	}
}
namespace mystd{
	il int Max(int a,int b)<%if(a<b) return b;return a; %>
	il int Min(int a,int b)<%if(a>b) return b;return a; %>
	il int Abs(int a)<% if(a<0) return a*(-1);return a; %>
	il double fMax(double a,double b)<%if(a<b) return b;return a; %>
	il double fMin(double a,double b)<%if(a>b) return b;return a; %>
	il double fAbs(double a)<% if(a<0) return a*(-1);return a; %>
	il int dcmp(double a){
		if(a<-eps)	return -1;
		if(a>eps)	return 1;
		return 0;
	}
}const int maxn=1200500;

int T,n,m;
int dep[maxn],myf[maxn],sonum[maxn],top[maxn],hson[maxn],in[maxn],myin[maxn],tim;
int pos[maxn],du[maxn];
int t,head[maxn<<6];
vector<int> E[maxn]; 
struct edge{
	int v,next;
};edge e[maxn<<6];
il void add_edge(int u,int v){
	e[++t].v=v;
	e[t].next=head[u];
	head[u]=t;
}

namespace SegementTree{
	#define lid (id<<1)
	#define rid (id<<1|1)
	int S[maxn<<2],T[maxn<<2];
	void build_tree(int id,int l,int r){
		if(l==r){
			pos[myin[l]]=id;
			return;
		}
		add_edge(id,lid);++du[lid];
		add_edge(id,rid);++du[rid];
		add_edge((n<<2)+lid,(n<<2)+id);++du[(n<<2)+id];
		add_edge((n<<2)+rid,(n<<2)+id);++du[(n<<2)+id];
		int mid=(l+r)>>1;
		build_tree(lid,l,mid);
		build_tree(rid,mid+1,r);
	}
	void update(int id,int l,int r,int x,int y,int p){
		if(x>r || y<l)	return;
		if(x<=l && r<=y){
			add_edge(p,id);++du[id];
			add_edge((n<<2)+id,p);++du[p];
			return;
		}
		int mid=(l+r)>>1;
		update(lid,l,mid,x,y,p);
		update(rid,mid+1,r,x,y,p);
	}
	void update1(int id,int l,int r,int x,int y,int p){
		if(x>r || y<l || x>y)	return;
		if(x<=l && r<=y){
			add_edge(p,id);
			++du[id];
			return;
		}
		int mid=(l+r)>>1;
		update1(lid,l,mid,x,y,p);
		update1(rid,mid+1,r,x,y,p);
	}
	void update2(int id,int l,int r,int x,int y,int p){
		if(x>r || y<l || x>y)	return;
		if(x<=l && r<=y){
			add_edge((n<<2)+id,p);
			++du[p];
			return;
		}
		int mid=(l+r)>>1;
		update2(lid,l,mid,x,y,p);
		update2(rid,mid+1,r,x,y,p);
	}
	#undef lid
	#undef rid
}

il void dfs1(int now,int fa){
	myf[now]=fa;
	dep[now]=dep[fa]+1;
	sonum[now]=1;
	for(int to:E[now]){
		if(to==fa)	continue;
		dfs1(to,now);
		sonum[now]+=sonum[to];
		if(sonum[hson[now]]<sonum[to])	hson[now]=to;
	}
}

il void dfs2(int now,int topp){
	top[now]=topp;
	in[now]=++tim;
	myin[tim]=now;
	if(!hson[now])	return;
	dfs2(hson[now],topp);
	for(int to:E[now]){
		if(to!=myf[now] && to!=hson[now])	dfs2(to,to);
	}
}

il void update(int u,int v,int id){
	add_edge(n*8+id,(n<<2)+pos[u]);++du[(n<<2)+pos[u]];
	add_edge(pos[v],n*8+id);++du[n*8+id];
	int x=u,fx=top[x],y=v,fy=top[y];
	while(fx!=fy){
		if(dep[fx]>dep[fy])	swap(fx,fy),swap(x,y);
		if(y!=u && y!=v)	SegementTree::update(1,1,n,in[fy],in[y],8*n+id);
		else{
			SegementTree::update(1,1,n,in[fy],in[y]-1,8*n+id);
			if(y==u)	add_edge(8*n+id,pos[u]),++du[pos[u]];
			else	add_edge(4*n+pos[v],8*n+id),++du[8*n+id];
			
		}
		y=myf[top[y]],fy=top[y];
	}
	
	if(dep[x]>dep[y])	swap(x,y);
	if(x!=v && y!=v)	SegementTree::update1(1,1,n,in[x],in[y],8*n+id);
	else if(x!=y){
		if(x==v)	SegementTree::update1(1,1,n,in[x]+1,in[y],8*n+id);
		else	SegementTree::update1(1,1,n,in[x],in[y]-1,8*n+id); 
	}
	if(x!=u && y!=u)	SegementTree::update2(1,1,n,in[x],in[y],8*n+id);
	else if(x!=y){
		if(x==u)	SegementTree::update2(1,1,n,in[x]+1,in[y],8*n+id);
		else	SegementTree::update2(1,1,n,in[x],in[y]-1,8*n+id);
	}
}

queue<int> q;
il void inttopo(){
	for(int i=1;i<=n*8+m;++i){
		if(du[i]==0)	q.push(i);
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(rg i=head[u];i;i=e[i].next){
			int to=e[i].v;
			--du[to];
			if(du[to]==0)	q.push(to);
		}
	}
}

il void clear(){
	tim=0;
	t=0;
	for(rg i=1;i<=n;++i)	<% myf[i]=dep[i]=sonum[i]=hson[i]=in[i]=myin[i]=top[i]=0;E[i].clear(); %>
	for(rg i=1;i<=n*8+m;++i)	head[i]=du[i]=0;
}

il void input(){
	n=io::read();
	int u,v;
	for(rg i=1;i<=n-1;++i){
		u=io::read(),v=io::read();
		E[u].push_back(v);
		E[v].push_back(u);
	}
}

int main(){
//	freopen("prison.in","r",stdin);
//	freopen("prison.out","w",stdout);
	T=io::read(); 
	while(T--){
		input();
		dfs1(1,0);
		dfs2(1,1);
		SegementTree::build_tree(1,1,n);
		m=io::read();
		int s,t;
		for(rg i=1;i<=m;++i){
			scanf("%d %d",&s,&t);
			update(s,t,i);
		}
//		for(rg i=1;i<=n*8+m;++i){
//			cout<<i<<' '<<du[i]<<endl;
//		}
		inttopo();
		bool mj=true;
		for(int i=1;i<=8*n+m;++i){
			if(du[i])	<% mj=false;break; %>
		}
		if(mj)	printf("Yes\n");
		else	printf("No\n");
		clear();
	}
	return 0;
}
/*
1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 5
2 6
3 7
4 8
*/