0 pts实在调不动了,第三个样例卡死了,悬棺
查看原帖
0 pts实在调不动了,第三个样例卡死了,悬棺
1037997
_TGWQ12_楼主2025/7/20 13:38
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,P=1e9+7,inv2=P+1>>1;
int nxt[N<<1],head[N],to[N<<1],tot=1,in[N];
int fac[N],inv[N],dfn[N],dp[N];
bool vis[N];
int n,m,x,y,f[N];
int C,t;
void add(int x,int y){
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
	in[x]++;
}
int Pow(int a,int b){
	int cnt=1,num=a;
	while(b){
		if(b&1) cnt=(num*cnt)%P;
		num=num*num%P;
		b>>=1;
	}
	return cnt;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%P;
	int nac=Pow(fac[n],P-2);
	for(int i=n;i>=1;i--){
		inv[i]=nac*fac[i-1];
		nac=nac*i%P;
	}
	inv[0]=1;
}
void dfs(int cur,int id){
	if(t==8)cout<<cur<<'\n';
	for(int i=head[cur];i;i=nxt[i]){
		if((i^1)==id) continue;
		dfs(to[i],i);
		(dp[cur]+=dp[to[i]])%=P;
		if(vis[i>>1]){
			(dp[cur]+=f[to[i]]*inv[in[cur]-1])%=P;
			(f[cur]+=inv[in[to[i]]-1])%=P;
		}
		else
			(f[cur]+=f[to[i]])%=P;
	}
	f[cur]=f[cur]*inv[in[cur]-1]%P;
}
void clean(){
	tot=1;
	for(int i=1;i<=n;i++)
		dp[i]=in[i]=f[i]=head[i]=vis[i]=0;
} 
void work(){
	cin>>n>>m;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=m;i++){
		cin>>x;
		vis[x]=1;
	}
	int ans=1;
	for(int i=1;i<=n;i++)
		(ans*=fac[in[i]-1])%=P;
	dfs(1,0);
	cout<<((ans*((m-dp[1])%P))%P+P)%P<<'\n';
	clean();
}
signed main() {
//	freopen("traverse3.in","r",stdin);;
	cin>>C>>t;
	init(1e5);
	while(t--){
		work();
	}
  	return 0;
}


2025/7/20 13:38
加载中...