C++(g++ 7.5.0) 解法, 执行用时: 149ms, 内存消耗: 23052K, 提交时间: 2022-10-13 14:11:29

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int N=100005;
const int mod=1e9+7;
int n;
ll x,y,a,b,z;
ll p[N],d[N],f[N];
vector<pii> E[N];
vector<int> v[N];
ll sum,res,ans,sub;
inline ll qpow(ll x,ll y)
{
	ll res=1;
	while(y)
	{
		if(y&1)res=res*x%mod;
		y>>=1;
		x=x*x%mod;
	}
	return res;
}
void dfs(int x,int fa)
{
	d[x]=d[fa]+1;
	v[d[x]].pb(x);
	f[x]=(1-p[x]+mod)%mod;
	for(auto y:E[x])
	{
		if(y.fi==fa)continue;
		dfs(y.fi,x);
		f[x]=f[x]*(f[y.fi]+(1-f[y.fi]+mod)*(1-y.se+mod)%mod)%mod;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>x>>y;
		p[i]=x*qpow(y,mod-2)%mod;
	}
	for(int i=1;i<n;++i)
	{
		cin>>x>>y>>a>>b;
		z=a*qpow(b,mod-2)%mod;
		E[x].pb(mp(y,z));
		E[y].pb(mp(x,z));
	}
	dfs(1,0);
	ans=(1-f[1]+mod)%mod;
	sum=1;
	for(int i=2;i<=n;++i)
	{
		if(!v[i].size())break;
		sub=res=1;
		for(auto x:v[i-1])
		{
			res=res*f[x]%mod;
			sub=sub*(1-p[x]+mod)%mod;
		}
		for(auto x:v[i])
		{
			sub=sub*f[x]%mod;
		}
		res=(res+mod-sub)%mod;
		ans+=res*sum%mod*i%mod;
		if(ans>=mod)ans-=mod;
		for(auto x:v[i-1])
			sum=sum*(1-p[x]+mod)%mod;
	}
	cout<<ans;
}

C++ 解法, 执行用时: 97ms, 内存消耗: 23808K, 提交时间: 2022-06-10 14:45:44

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mo=1e9+7;
using pp=pair<int,int>;
int n,x,y,u,v,ans,a[N],dep[N],f[N],g[N];
vector<pp>p[N];
vector<int>q[N];
int ksm(int x,int y)
{
	int t=1;
	for (;y;y>>=1)
	{
		if (y&1) t=1ll*t*x%mo;
		x=1ll*x*x%mo;
	}
	return t;
}
void dg(int x,int y)
{
	dep[x]=dep[y]+1;
	q[dep[x]].emplace_back(x);
	f[x]=(mo+1-a[x])%mo;
	for (auto t:p[x])
	if (t.first^y)
	{
		g[t.first]=t.second;
		dg(t.first,x);
		f[x]=1ll*f[x]*(mo+1-1ll*f[t.first]%mo*t.second%mo)%mo;
	}
	f[x]=(mo+1-f[x])%mo;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>x>>y;
		a[i]=1ll*x*ksm(y,mo-2)%mo;
	}
	for (int i=1;i<n;i++)
	{
		cin>>x>>y>>u>>v;
		int z=1ll*u*ksm(v,mo-2)%mo;
		p[x].emplace_back(y,z);
		p[y].emplace_back(x,z);
	}
	dg(1,0);
	int s=1;
	for (int i=1;i<=n;i++)
	{
		int w=1,w1=1;
		for (auto t:q[i]) 
		{
			w=1ll*w*(mo+1-1ll*f[t]*g[t]%mo)%mo;
			w1=1ll*w1*(mo+1-f[t])%mo;
		}
		w=(w-w1+mo)%mo;
		ans=(ans+1ll*w*s%mo*i)%mo;
		for (auto t:q[i]) s=1ll*s*(mo+1-a[t])%mo;
	}
	cout<<ans;
	return 0;
}