rt

实在卡不动了（为什么不能多给一秒

卡常前的代码（88pts，11.85s，样例 6 本地 3s）

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
const ll N=5e5+2,M=(1<<20)+2,P=1e9+7;
ll n,m,k,d,ans,c[N],h[N],w[N],w0[N],w1[N];
ll pw[N],pi[N],dfn[N],dfm[N],f[N][20];
vector<ll>e[N],E[N];
vector<pii>b[N];
namespace SGT{
	ll a[M],d[M];
	void init(ll x=1,ll l=1,ll r=n){
		a[x]=r-l+1,d[x]=1;
		if(l==r)return;
		init(x<<1,l,l+r>>1);
		init(x<<1|1,l+r+2>>1,r);
	}
	ll opt(ll L,ll R,ll c=1,ll x=1,ll l=1,ll r=n){
		if(l>R||L>r||L>R||l>r)return 0;
		if(L<=l&&r<=R)return(d[x]*=c)%=P,(a[x]*=c)%=P;
		ll s=opt(L,R,c,x<<1,l,l+r>>1);
		s+=opt(L,R,c,x<<1|1,l+r+2>>1,r);
		a[x]=(a[x<<1]+a[x<<1|1])*d[x]%P;
		return s*d[x]%P;
	}
}
using SGT::opt;
void dfs(ll x,ll y){
	dfn[x]=++d,h[x]=h[y]+1,f[x][0]=y;
	for(ll i=1;i<20;i++)
		f[x][i]=f[f[x][i-1]][i-1];
	for(ll i:e[x])
		if(i!=y)dfs(i,x);
	dfm[x]=d;
}
ll lca(ll x,ll y){
	if(h[x]<h[y])swap(x,y);
	for(ll i=19;~i;i--)
		if(h[f[x][i]]>=h[y])x=f[x][i];
	for(ll i=19;~i;i--)
		if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	if(x!=y)x=f[x][0];
	return x;
}
ll fa(ll x,ll y){
	for(ll i=19;~i;i--)
		if(h[f[x][i]]>h[y])x=f[x][i];
	return x;
}
void Dfs(ll x){
	w0[x]=w[x];
	for(ll i:e[x])
		if(h[x]<h[i])Dfs(i),w0[x]+=w0[i];
}
void dFs(ll x,ll y){
	if(y)w1[x]+=w1[y]+w0[y]-w[y]-w0[x];
	for(ll i:e[x])
		if(i!=y)dFs(i,x);
}
void dfS(ll x){
	ll s=1,p=1,g=0,y;
	for(ll i:e[x])
		if(h[x]<h[i])dfS(i);
	for(ll i:E[x])opt(dfn[i],dfm[i],2);
	for(ll i:e[x])
		if(h[x]<h[i])
			y=opt(dfn[i],dfm[i]),
			(s*=y+1)%=P,(p*=pw[w0[i]])%=P,(g+=y)%=P;
	g=(-g-1+(!c[x])*s)%P,s=y=0;
	map<ll,vector<pair<pii,ll>>>q;
	map<ll,ll>t;
	q[dfn[x]+1],q[dfm[x]+1];
	for(pii i:b[x])
		q[dfn[i.fi]].pb({{dfn[i.se],dfm[i.se]},2}),
		q[dfm[i.fi]+1].pb({{dfn[i.se],dfm[i.se]},pi[1]});
	for(auto&i:q)t[y]=opt(y,i.fi-1),y=i.fi;
	for(auto&i:q){
		for(auto&j:i.se)opt(j.fi.fi,j.fi.se,j.se);
		(s+=opt(dfn[x]+1,dfm[x])*t[i.fi])%=P;
	}
	y=opt(dfn[x]+1,dfm[x]),s=(s-y*y)%P*pi[1]%P;
	(ans+=(s+g)*p%P*pw[w1[x]])%=P;
	opt(dfn[x],dfn[x],g*p%P*pi[w0[x]]%P);
	opt(dfn[x]+1,dfm[x],pi[w[x]]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>n>>m>>k;
	for(ll i=1,x,y;i<n;i++)
		cin>>x>>y,e[x].pb(y),e[y].pb(x);
	dfs(1,0),pw[0]=pi[0]=1,SGT::init();
	for(ll i=1,x,y,z;i<=m;i++){
		cin>>x>>y,z=lca(x,y);
		if(h[x]>h[y])swap(x,y);
		if(x==z)E[x].pb(y),w[fa(y,x)]++;
		else w1[x]++,b[z].pb({x,y}),b[z].pb({y,x});
		w1[y]++;
		pw[i]=pw[i-1]*2%P,pi[i]=pi[i-1]*(P+1)/2%P;
	}
	for(ll i=1,x;i<=k;i++)cin>>x,c[x]=1;
	Dfs(1),dFs(1,0),dfS(1);
	cout<<(P-ans)%P;
	return 0;
}

卡常后的代码（92pts，9.92s，样例 6 本地 2s）

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const ll N=5e5+2,M=(1<<20)+2,P=1e9+7;
int n,m,k,d,c[N],h[N],w[N],w0[N],w1[N];
int dfn[N],dfm[N],f[N][20],e[N],E[N];
ll ans,t[N],pw[N],pi[N];
vector<pii>b[N];
char buf[1<<14],*p1,*p2;
int o,B[M*2],C[M*2];
#define F(Y,X) for(int _=X,Y;Y=C[_],_;_=B[_])
#define gc (p1==p2?p2=buf+fread(p1=buf,1,1<<14,stdin),p1==p2?EOF:*p1++:*p1++)
inline int pu(int&x,int y){return B[++o]=x,C[o]=y,x=o;}
inline int rd(int x=0,char c=gc){
	while(c<'0'||c>'9')c=gc;
	while('0'<=c&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc;
	return x;
}
namespace SGT{
	ll a[M],d[M];
	void init(int x=1,int l=1,int r=n){
		a[x]=r-l+1,d[x]=1;
		if(l==r)return;
		init(x<<1,l,l+r>>1);
		init(x<<1|1,l+r+2>>1,r);
	}
	inline ll opt(int L,int R,ll c=1,int x=1,int l=1,int r=n){
		if(l>R||L>r||L>R||l>r)return 0;
		if(L<=l&&r<=R)return(d[x]*=c)%=P,(a[x]*=c)%=P;
		ll s=opt(L,R,c,x<<1,l,l+r>>1);
		s+=opt(L,R,c,x<<1|1,l+r+2>>1,r);
		a[x]=(a[x<<1]+a[x<<1|1])*d[x]%P;
		return s*d[x]%P;
	}
}
using SGT::opt;
int dfs(int x,int y){
	dfn[x]=++d,h[x]=h[y]+1,f[x][0]=y;
	for(int i=1;i<20;i++)
		f[x][i]=f[f[x][i-1]][i-1];
	F(i,e[x])
		if(i!=y)dfs(i,x);
	return dfm[x]=d;
}
int lca(int x,int y){
	if(h[x]<h[y])swap(x,y);
	for(int i=19;~i;i--)
		if(h[f[x][i]]>=h[y])x=f[x][i];
	for(int i=19;~i;i--)
		if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	if(x!=y)x=f[x][0];
	return x;
}
int fa(int x,int y){
	for(int i=19;~i;i--)
		if(h[f[x][i]]>h[y])x=f[x][i];
	return x;
}
int Dfs(int x){
	w0[x]=w[x];
	F(i,e[x])
		if(h[x]<h[i])Dfs(i),w0[x]+=w0[i];
	return 0;
}
int dFs(int x,int y){
	if(y)w1[x]+=w1[y]+w0[y]-w[y]-w0[x];
	F(i,e[x])
		if(i!=y)dFs(i,x);
	return 0;
}
int dfS(int x){
	ll s=1,p=1,g=0,y;
	F(i,e[x])
		if(h[x]<h[i])dfS(i);
	F(i,E[x])opt(dfn[i],dfm[i],2);
	F(i,e[x])
		if(h[x]<h[i])
			y=opt(dfn[i],dfm[i]),
			(s*=y+1)%=P,(p*=pw[w0[i]])%=P,(g+=y)%=P;
	g=(-g-1+(c[x]?0:s))%P,s=y=0;
	map<int,vector<pair<pii,int>>>q;
	q[dfn[x]+1],q[dfm[x]+1];
	for(pii i:b[x])
		q[dfn[i.fi]].pb({{dfn[i.se],dfm[i.se]},2}),
		q[dfm[i.fi]+1].pb({{dfn[i.se],dfm[i.se]},pi[1]});
	for(auto&i:q)t[y]=opt(y,i.fi-1),y=i.fi;
	for(auto&i:q){
		for(auto&j:i.se)opt(j.fi.fi,j.fi.se,j.se);
		(s+=opt(dfn[x]+1,dfm[x])*t[i.fi])%=P;
	}
	y=opt(dfn[x]+1,dfm[x]),s=(s-y*y)%P*pi[1]%P;
	(ans+=(s+g)*p%P*pw[w1[x]])%=P;
	opt(dfn[x],dfn[x],g*p%P*pi[w0[x]]%P);
	return opt(dfn[x]+1,dfm[x],pi[w[x]]);
}
int main(){
	rd(),n=rd(),m=rd(),k=rd();
	for(int i=1,x,y;i<n;i++)
		x=rd(),y=rd(),pu(e[x],y),pu(e[y],x);
	dfs(1,0),pw[0]=pi[0]=1,SGT::init();
	for(int i=1,x,y,z;i<=m;i++){
		x=rd(),y=rd(),z=lca(x,y);
		if(h[x]>h[y])swap(x,y);
		if(x==z)pu(E[x],y),w[fa(y,x)]++;
		else w1[x]++,b[z].pb({x,y}),b[z].pb({y,x});
		w1[y]++,pw[i]=pw[i-1]*2%P,pi[i]=pi[i-1]*(P+1)/2%P;
	}
	for(int i=1,x;i<=k;i++)x=rd(),c[x]=1;
	Dfs(1),dFs(1,0),dfS(1);
	cout<<(P-ans)%P;
	return 0;
}

ps：线段树递归传参优化已经尝试过了，但是好像是负优化。（下面是优化的线段树代码）

namespace SGT{
	ll a[M],d[M],l[M],r[M],L,R,c;
	void init(ll x=1,ll l_=1,ll r_=n){
		a[x]=r_-l_+1,d[x]=1;
		l[x]=l_,r[x]=r_;
		if(l_==r_)return;
		init(x<<1,l_,l_+r_>>1);
		init(x<<1|1,l_+r_+2>>1,r_);
	}
	inline ll mdf(ll x){
		if(l[x]>R||L>r[x])return 0;
		if(L<=l[x]&&r[x]<=R)
			return(d[x]*=c)%=P,(a[x]*=c)%=P;
		ll s=mdf(x<<1)+mdf(x<<1|1);
		a[x]=(a[x<<1]+a[x<<1|1])*d[x]%P;
		return s*d[x]%P;
	}
	inline ll opt(ll l_,ll r_,ll t=1){
		if(l_>r_)return 0;
		return L=l_,R=r_,c=t,mdf(1);
	}
}