50分求助
查看原帖
50分求助
1405472
NiChenhang楼主2024/10/27 16:35

不知道为什么最后五个点一直拿不到

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
struct rec {
	int ans,size;
}score[2000010];
int s[2000010],mod = 19260817;
int ver[4000010],head[2000010],Next[4000010],tot = 1;
int m,n;int inv[200010],que[200010];
bitset<200010> check;
inline void read(int &out) {
	out = 0;
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9')out = out*10+(c-'0'),c = getchar();
	return ;
}
inline void add(int x,int y) {
	ver[++tot] = y;Next[tot] = head[x];head[x] = tot;
	ver[++tot] = x;Next[tot] = head[y];head[y] = tot;
}
inline int mul_self(int x,int p) {
	int ans = 1;
	for(;p;p>>=1) {
		if(p&1) ans = (ll)ans*x%mod;
		x = (ll)x*x%mod;
	}
	return ans;
}
inline int get_inv(int p){
	if(inv[p]) return inv[p];
	if(!(p - (p&-p))) {
		inv[p] = get_inv(p>>1);
		inv[p] = (ll)inv[p]*inv[p]%mod;
		return inv[p];
	}
	int ans = 1;
	for(;p;p -= (p&-p)){
		ans = (ll)get_inv(p&-p)*ans%mod;
	}
	return ans;
}
void dfs(int x) {
	if(check.none()) return;
	score[x].ans = ((ll)s[x]+1)%mod*inv[1]%mod;score[x].size = 1;
	for(int i = head[x];i;i = Next[i]) {
		int y =ver[i];
		if(score[y].size) continue;
		dfs(y);
		score[x].ans = (ll)score[x].ans*score[y].ans%mod;
		score[x].size += score[y].size;
		if(check.none()) return;
	}
	if(check[x])check[x] = false;
}

int main(){
 	inv[1] = mul_self(2,19260815);check.reset();
	read(n);read(m);
	for(int i = 1;i <= n;i++) read(s[i]);
	for(int i = 1;i < n;i++) {
		int u,v;read(u);read(v);
		add(u,v);
	}
	int sum = 0;
	for(int i = 0;i < m;i++) {
		read(que[i]);
		check[que[i]] = true;
	}
	dfs(1);
	for(int i = 0;i < m;i++) {
		int x = que[i];
		sum = ((ll)sum + ((ll)score[x].ans+mod-get_inv(score[x].size))%mod)%mod;
	}
	cout<<sum;
}
2024/10/27 16:35
加载中...