Description

Input

Output

Sample Input

输入1：

5 3 1
1 4
4 2
1 5
4 3
1 3
1 4
2 4
3 2

输入2：

10 5 4
10 3
6 9
6 3
6 8
9 5
1 8
6 4
7 3
6 2
1 10
6 9
6 8
4 5
1 9
1 5
5 2
1 3
3 2

Sample Output

输出1：

3 1 2

输出2：

1 5 3 4 2

Data Constraint

Solution

• 这题我打的是二维线段树（树上每个点代表一个矩形，将长割一半作为两个子节点）。

• 每条路径 $(x,y)$(x,y) 加入二维线段树的位置 $(dfn[x],dfn[y])$(dfn[x],dfn[y]) 上，这里要保证 $dfn[x]&lt;dfn[y]$dfn[x]<dfn[y] 。

• 那么我们要查询每条路径被哪些路径包含，就相当于在线段树上查询一个或两个矩形。

• 注意查询的时候也要保证矩形的左下角 $(x,y)$(x,y) 满足 $x&lt;y$x<y ，这样避免了很多讨论。

• 线段树优化连边后跑拓扑排序即可。

• 时间复杂度 $O(n\ log^2n)$O(n log2n) 。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cctype>
using namespace std;
const int N=1e5+5,M=20;
struct data
{
	int l,r;
}f[N*M+N];
int tot,cnt,qx,qy,qxx,qyy,qz,rt;
int first[N*M],nex[N*M*M/2],en[N*M*M/2],d[N*M];
int dfn[N],size[N],fa[N][17],dep[N];
int a[N],b[N],c[N],q[N*M];
inline int read()
{
	int X=0,w=0; char ch=0;
	while(!isdigit(ch)) w|=ch=='-',ch=getchar();
	while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
	return w?-X:X;
}
void write(int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
inline void insert(int x,int y)
{
	nex[++tot]=first[x];
	first[x]=tot;
	en[tot]=y;
}
inline void insert1(int x,int y)
{
	nex[++tot]=first[x];
	first[x]=tot;
	en[tot]=y;
	d[y]++;
}
void dfs(int x)
{
	dfn[x]=++tot;
	size[x]=1;
	dep[x]=dep[fa[x][0]]+1;
	for(int i=first[x];i;i=nex[i])
		if(en[i]^fa[x][0])
		{
			fa[en[i]][0]=x;
			dfs(en[i]);
			size[x]+=size[en[i]];
		}
}
void change(int &v,int pre,int xl,int xr,int yl,int yr)
{
	if(!v)
	{
		if(xl==xr && yl==yr) v=qz; else v=++cnt;
		if(pre) insert1(v,pre);
	}
	if(xl==xr && yl==yr) return;
	if(xr-xl>yr-yl)
	{
		int mid=xl+xr>>1;
		if(qx<=mid) change(f[v].l,v,xl,mid,yl,yr); else
			change(f[v].r,v,mid+1,xr,yl,yr);
	}else
	{
		int mid=yl+yr>>1;
		if(qy<=mid) change(f[v].l,v,xl,xr,yl,mid); else
			change(f[v].r,v,xl,xr,mid+1,yr);
	}
}
void find(int v,int xl,int xr,int yl,int yr)
{
	if(!v) return;
	if(qx<=xl && xr<=qy)
		if(qxx<=yl && yr<=qyy)
		{
			if(qz^v) insert1(v,qz);
			return;
		}
	if(xr-xl>yr-yl)
	{
		int mid=xl+xr>>1;
		if(qx<=mid) find(f[v].l,xl,mid,yl,yr);
		if(qy>mid) find(f[v].r,mid+1,xr,yl,yr);
	}else
	{
		int mid=yl+yr>>1;
		if(qxx<=mid) find(f[v].l,xl,xr,yl,mid);
		if(qyy>mid) find(f[v].r,xl,xr,mid+1,yr);
	}
}
inline int lca(int x,int y)
{
	for(int i=log2(dep[x]);i>=0;i--)
		if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if(x==y) return x;
	for(int i=log2(dep[x]);i>=0;i--)
		if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int main()
{
	freopen("stier.in","r",stdin);
	freopen("stier.out","w",stdout);
	int n=read(),m=read(),k=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		insert(x,y);
		insert(y,x);
	}
	tot=0;
	dfs(1);
	for(int j=1;j<17;j++)
		for(int i=1;i<=n;i++)
			fa[i][j]=fa[fa[i][j-1]][j-1];
	tot=0;
	memset(first,0,sizeof(first));
	cnt=m;
	for(int i=1;i<=m;i++)
	{
		a[i]=read(),b[i]=read();
		if(dep[a[i]]<dep[b[i]]) swap(a[i],b[i]);
		c[i]=lca(a[i],b[i]);
		qx=dfn[a[i]];
		qy=dfn[b[i]];
		if(qx>qy) swap(qx,qy);
		qz=i;
		change(rt,0,1,n,1,n);
	}
	for(int i=1;i<=k;i++)
	{
		int x=read(),y=read();
		insert1(x,y);
	}
	for(int i=1;i<=m;i++)
	{
		qz=i;
		if(c[i]==b[i])
		{
			int pos=a[i];
			for(int j=log2(dep[pos]);j>=0;j--)
				if(dep[fa[pos][j]]>dep[b[i]]) pos=fa[pos][j];
			qx=dfn[a[i]];
			qy=dfn[a[i]]+size[a[i]]-1;
			qxx=1;
			qyy=dfn[b[i]]-1;
			if(qx>qxx) swap(qx,qxx),swap(qy,qyy);
			if(qx<=qy && qxx<=qyy) find(rt,1,n,1,n);
			qx=dfn[a[i]]+1;
			qy=dfn[a[i]]+size[a[i]]-1;
			qxx=1;
			qyy=dfn[pos]-1;
			if(qx>qxx) swap(qx,qxx),swap(qy,qyy);
			if(qx<=qy && qxx<=qyy) find(rt,1,n,1,n);
			qx=dfn[a[i]];
			qy=dfn[a[i]]+size[a[i]]-1;
			qxx=dfn[b[i]]+1;
			qyy=dfn[pos]-1;
			if(qx>qxx) swap(qx,qxx),swap(qy,qyy);
			if(qx<=qy && qxx<=qyy) find(rt,1,n,1,n);
			qx=dfn[a[i]];
			qy=dfn[a[i]]+size[a[i]]-1;
			qxx=dfn[pos]+size[pos];
			qyy=n;
			if(qx>qxx) swap(qx,qxx),swap(qy,qyy);
			if(qx<=qy && qxx<=qyy) find(rt,1,n,1,n);
		}else
		{
			if(dfn[a[i]]>dfn[b[i]]) swap(a[i],b[i]);
			qx=dfn[a[i]]+1;
			qy=dfn[a[i]]+size[a[i]]-1;
			qxx=dfn[b[i]];
			qyy=dfn[b[i]]+size[b[i]]-1;
			if(qx<=qy) find(rt,1,n,1,n);
			qx=dfn[a[i]];
			qy=dfn[a[i]]+size[a[i]]-1;
			qxx=dfn[b[i]]+1;
			qyy=dfn[b[i]]+size[b[i]]-1;
			if(qxx<=qyy) find(rt,1,n,1,n);
		}
	}
	int l=0,r=0;
	for(int i=1;i<=cnt;i++)
		if(!d[i]) q[++r]=i;
	while(l<r)
	{
		int x=q[++l];
		if(x<=m) write(x),putchar(' ');
		for(int i=first[x];i;i=nex[i])
			if(!--d[en[i]]) q[++r]=en[i];
	}
	return 0;
}