自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:40:18，当前版本为作者最后更新于2022-10-09 15:23:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 比较板的三维偏序。

• 不会三维偏序的可以先转这儿

首先拿到题，不难发现如果给定的不是一棵树而是序列，那就是完全的板子题。

考虑如何向原问题转化：当然是要按照某个“序”将树变成序列，那怎么知道应该按照什么“序”呢？

让我们回归问题本身，题目要求的是求每个节点为根的子树内的二维偏序，那这个“序”当然需要满足同一子树内的节点在“序”中编号都大于/小于根节点，容易想到 dfs 序就满足条件。

• 按 dfs 序给每个点编号，那题目就转化为对每个点 $u$ 求出满足如下要求的点 $v$ 的个数：

1. $red_v \leq red_u$

2. $blue_v \leq blue_u$

3. $dfn_u < dfn_v < dfn_u + sz_u$

那么直接做三维偏序就行了，下附代码：

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x)	x&-x
#define mid ((L+R)>>1)
const int N=2e5+10;
int n,now,ans[N],C[N];
int h[N],e[N<<1],ne[N<<1],idx;
struct node
{
	int red,blue,dfn,sz,id;
	bool operator<(const node other)const
	{
		if(red!=other.red)	return red<other.red;
		if(blue!=other.blue)	return blue<other.blue;
		return dfn>other.dfn;
	}
}p[N],tmp[N];
inline void link(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
inline void dfs(int u,int fa)
{
	p[u].dfn=++now;
	p[u].sz=1;
	for(int i=h[u];~i;i=ne[i])
	{
		if(e[i]==fa)	continue;
		dfs(e[i],u);
		p[u].sz+=p[e[i]].sz;
	}
}
inline void add(int x,int y)
{
	for(;x<=n;x+=lowbit(x))	C[x]+=y;
}
inline int query(int x)
{
	int ans=0;
	for(;x;x-=lowbit(x))	ans+=C[x];
	return ans;
}
inline void mergesort(int L,int R)
{
	if(L==R)	return void();
	mergesort(L,mid);
	mergesort(mid+1,R);
	int i=L,j=mid+1,t=0;
	while(i<=mid&&j<=R)
		if(p[i].blue<=p[j].blue)	add(p[i].dfn,1),tmp[++t]=p[i],i++;
		else ans[p[j].id]+=query(min(p[j].dfn+p[j].sz-1,n))-query(p[j].dfn),tmp[++t]=p[j],j++;
	while(i<=mid)	add(p[i].dfn,1),tmp[++t]=p[i],i++;
	while(j<=R)	ans[p[j].id]+=query(min(p[j].dfn+p[j].sz-1,n))-query(p[j].dfn),tmp[++t]=p[j],j++;
	for(int i=L;i<=mid;i++)	add(p[i].dfn,-1);
	for(int i=L,j=1;i<=R;i++,j++)	p[i]=tmp[j];
}
int main()
{
	memset(h,-1,sizeof h);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	p[i].id=i;
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		link(u,v),link(v,u);
	}
	dfs(1,-1);
	for(int i=1;i<=n;i++)	scanf("%d%d",&p[i].red,&p[i].blue);
	sort(p+1,p+n+1);
	mergesort(1,n);
	for(int i=1;i<=n;i++)	if(ans[i])	printf("%d\n",ans[i]);
	return 0;
}

• 完结撒花~