D Genealogy in the trees

考虑把树拍平到 dfn 序列上，那么题目要求即为对于每个 求有多少点对 满足：

其中 为点 子树大小，但本式中最后一部分不需要显式处理 ，只需在结点 退栈时记录 时间戳即可。

放到二维平面上，将第一个式子的元素作为 轴坐标，第二个式子的元素作为 轴坐标，则每个点对可以被表示为线段，其中关键点对线段全部平行于 轴，询问点对线段全部平行于 轴。

则约束的式子在二维平面上的表现为关键点对线段与询问点对线段相交。

问题转化为：给定 条平行于 轴的线段， 次询问，每次询问给出一条平行于 轴的线段，问有多少条平行于 轴的线段与该线段相交。

典型二维数点，想咋搞咋搞，本人代码使用扫描线降维实现。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+11;
using ll=long long;
ll C[N*2];int _c;
void add(int x,ll v)
{
	while(x>0&&x<=_c) C[x]+=v,x+=(x&-x);
}
ll sum(int x)
{
	ll r=0;
	while(x>0) r+=C[x],x-=(x&-x);
	return r;
}
int dfnl[N],dfnr[N],dfc;
struct edge
{
	int t,nxt;
}G[N*2];int at[N],ct;
inline void add_edge(int u,int v)
{
	G[++ct]={v,at[u]};at[u]=ct;
}
void dfs(int u,int f)
{
	dfnl[u]=++dfc;
	for(int i=at[u];i;i=G[i].nxt)
	{
		auto v=G[i].t;if(v==f) continue;
		dfs(v,u);
	}
	dfnr[u]=dfc;
}
//dfnl[p]<=dfnl[a]<=dfnr[p]
//dfnl[b]<=dfnl[q]<=dfnr[b]
struct qs
{
	int l,r,id,pos;
}qrs[N*2];
struct evt
{
	int pos,p2,v;
}evs[N*2];
int n,m,q,u,v,cev;
ll ans[N];
int main()
{
    ios::sync_with_stdio(0);
	cin>>n>>m>>q;
	for(int i=1;i<n;++i)
	{
		cin>>u>>v;
		add_edge(u,v),add_edge(v,u);
	}
	dfs(1,0);_c=dfc+5;
	for(int i=1;i<=m;++i)
	{
		cin>>u>>v;
		evs[++cev]={dfnl[u],dfnl[v],1};
		evs[++cev]={dfnr[u]+1,dfnl[v],-1};		
	}
	for(int i=1;i<=q;++i)
	{
		cin>>u>>v;
		qrs[i]={dfnl[v],dfnr[v],i,dfnl[u]};
	}
	sort(evs+1,evs+1+cev,[](evt &a,evt &b) {return a.pos<b.pos;});
	sort(qrs+1,qrs+1+q,[](qs &a,qs &b) {return a.pos<b.pos;});
	int rptr=1;
	for(int i=1;i<=q;++i)
	{
		int np=qrs[i].pos;
		while(rptr<=cev&&evs[rptr].pos<=np) add(evs[rptr].p2,evs[rptr].v),++rptr;
		ans[qrs[i].id]=sum(qrs[i].r)-sum(qrs[i].l-1);
	}
	for(int i=1;i<=q;++i) cout<<ans[i]<<endl;
	return 0;
}