[ABC303E] A Gift From the Stars
每次合并都是合并入度为 \(1\) 的点，所以合并的一定不是中心，且被合并后入度是 \(2\)。因此如果某个节点的入度 \(\ge 3\)，那么这个节点一定是中心。对于剩余的点，因为保证有解，直接当作大小为 \(2\) 的星处理。（注意大小为 \(2\) 的星共 \(3\) 个点）。
#include<cstdio>
#include <cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
const int N=200010,mod=1e9+7;
int n,w[N],X,Y,fac[N],caf[N];
vector<int>g[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
#endif
// Insert Code Here
scanf("%d%d%d",&n,&X,&Y);
fac[0]=1;
E(i, n)fac[i]=fac[i-1]*1ll*i%mod;
int bs=fac[n],res=1,p=mod-2;
while(p){
if(p&1)res=1ll*res*bs%mod;
bs=1ll*bs*bs%mod;
p>>=1;
}
caf[n]=res;
Re(i, n-1, 0)caf[i]=caf[i+1]*(i+1ll)%mod;//阶乘逆元递推公式
E(i, n){
int tc,tw;
scanf("%d%d",&tc,&tw);
if(g[tc].empty())w[tc]=tw;
else w[tc]=min(w[tc],tw);
g[tc].push_back(tw);
}//统计每组的 min
int m1=0,m2=0;
E(i, n)
if(!g[i].empty()&&(!m1||w[i]<w[m1]))m1=i;
E(i, n)
if(!g[i].empty()&&i!=m1&&(!m2||w[i]<w[m2]))m2=i;
if(!m2||w[m1]+w[m2]>Y)return puts("1"),0;//获取m1,m2，并判断如果没有 m2（只有一种颜色），w[m1]+w[m2]>Y（即不同颜色之间不能连边），那颜色序列就是唯一的了。
int res1=0,res2=1;
E(i, n){
if(g[i].empty()||w[i]+w[m1]>Y)continue;
int cnt=0;
for(int v:g[i])cnt+=v+w[m1==i?m2:m1]<=Y||w[i]+v<=X;
res1+=cnt;
res2=res2*1ll*caf[cnt]%mod;
// (res2*=1ll*caf[cnt])%=mod;//注意这样写会导致溢出，因为等价于 res2*=1ll,res2*=caf[cnt]（GPT的见解）。
}
printf("%d",1ll*fac[res1]*res2%mod);
return 0;
}