漆器 • 1个月前
using namespace std;
static const int MOD = 1000000007; static const int MAXN = 500000 + 114;
int n, m, k; int vis[MAXN];
vector E[MAXN];
int Ldfn[MAXN], Rdfn[MAXN], dfncnt; int dep[MAXN], sz[MAXN], son[MAXN]; int topv[MAXN], fa[MAXN]; int nodeAt[MAXN];
void dfs1(int u){
sz[u] = 1;
dep[u] = dep[fa[u]] + 1;
for (size_t i = 0; i < E[u].size(); ++i){
int v = E[u][i];
if (v == fa[u]) continue;
fa[v] = u;
dfs1(v);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp){
topv[u] = tp;
Ldfn[u] = ++dfncnt;
nodeAt[dfncnt] = u;
if (son[u] != 0) dfs2(son[u], tp);
for (size_t i = 0; i < E[u].size(); ++i){
int v = E[u][i];
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
Rdfn[u] = dfncnt;
}
int LCA(int u, int v){
while (topv[u] != topv[v]){
if (dep[topv[u]] < dep[topv[v]]) std::swap(u, v);
u = fa[topv[u]];
}
if (dep[u] < dep[v]) std::swap(u, v);
return v;
}
int jump(int u, int v){
while (topv[u] != topv[v]){
if (fa[topv[u]] == v) return topv[u];
u = fa[topv[u]];
}
return nodeAt[Ldfn[v] + 1];
}
vector toson[MAXN]; int tofa[MAXN]; vector< pair<int,int> > xtr[MAXN];
int f[MAXN][3]; int sube[MAXN]; int sone[MAXN]; int pw2[MAXN]; int inv2[MAXN];
void DP1(int u){
sube[u] = (int)toson[u].size();
for (size_t i = 0; i < E[u].size(); ++i){
int v = E[u][i];
if (v == fa[u]) continue;
DP1(v);
sube[u] += sube[v];
}
}
int tr[MAXN<<2], tagv[MAXN<<2];
inline void pushup(int cur){
tr[cur] = ((long long)tr[cur<<1] + tr[cur<<1|1]) % MOD;
} inline void pushdown(int cur){
if (tagv[cur] == 1) return;
int t = tagv[cur];
tr[cur<<1] = (long long)tr[cur<<1] * t % MOD;
tagv[cur<<1] = (long long)tagv[cur<<1] * t % MOD;
tr[cur<<1|1] = (long long)tr[cur<<1|1] * t % MOD;
tagv[cur<<1|1] = (long long)tagv[cur<<1|1] * t % MOD;
tagv[cur] = 1;
} void change(int cur, int lt, int rt, int l, int r, int c){
if (rt < l || r < lt) return;
if (l <= lt && rt <= r){
tr[cur] = (long long)tr[cur] * c % MOD;
tagv[cur] = (long long)tagv[cur] * c % MOD;
return;
}
int mid = (lt + rt) >> 1;
pushdown(cur);
change(cur<<1, lt, mid, l, r, c);
change(cur<<1|1, mid+1, rt, l, r, c);
pushup(cur);
} void addPoint(int cur, int lt, int rt, int pos, int v){
if (lt == rt){
tr[cur] = (tr[cur] + v) % MOD;
return;
}
int mid = (lt + rt) >> 1;
pushdown(cur);
if (pos <= mid) addPoint(cur<<1, lt, mid, pos, v);
else addPoint(cur<<1|1, mid+1, rt, pos, v);
pushup(cur);
} int ask(int cur, int lt, int rt, int l, int r){
if (rt < l || r < lt) return 0;
if (l <= lt && rt <= r) return tr[cur];
int mid = (lt + rt) >> 1;
pushdown(cur);
long long res = 0;
res += ask(cur<<1, lt, mid, l, r);
res += ask(cur<<1|1, mid+1, rt, l, r);
return (int)(res % MOD);
}
int ans; int dpOut[MAXN]; int xtrval[MAXN]; int subkey[MAXN];
void DP2(int u){
subkey[u] = vis[u];
for (size_t i = 0; i < E[u].size(); ++i){
int v = E[u][i];
if (v == fa[u]) continue;
int cnt = sube[u] - sube[v] - sone[v] + tofa[v] + xtrval[v];
dpOut[v] = (long long)dpOut[u] * pw2[cnt] % MOD;
DP2(v);
subkey[u] += subkey[v];
}
}
vector Vtr[MAXN]; vector insv[MAXN]; int val, ql, qr, rootVT;
void DP4(int u){
if (u == rootVT){
qr = Rdfn[ Vtr[u][0] ];
for (size_t i = 1; i < Vtr[u].size(); ++i){
DP4(Vtr[u][i]);
qr = Rdfn[ Vtr[u][i] ];
}
return;
}
for (size_t i = 0; i < insv[u].size(); ++i){
int x = insv[u][i];
change(1, 1, n, Ldfn[x], Rdfn[x], 2);
}
int res = ask(1, 1, n, Ldfn[u], Rdfn[u]);
for (size_t i = 0; i < Vtr[u].size(); ++i){
int v = Vtr[u][i];
res = ((long long)res + MOD - ask(1, 1, n, Ldfn[v], Rdfn[v])) % MOD;
DP4(v);
}
res = (long long)res * ask(1, 1, n, ql, qr) % MOD;
val = (val + res) % MOD;
for (size_t i = 0; i < insv[u].size(); ++i){
int x = insv[u][i];
change(1, 1, n, Ldfn[x], Rdfn[x], (MOD + 1) / 2);
}
}
void DP3(int u){
for (size_t i = 0; i < E[u].size(); ++i){
int v = E[u][i];
if (v == fa[u]) continue;
DP3(v);
}
for (size_t i = 0; i < toson[u].size(); ++i){
int v = toson[u][i];
change(1, 1, n, Ldfn[v], Rdfn[v], 2);
}
for (size_t i = 0; i < E[u].size(); ++i){
int v = E[u][i];
if (v == fa[u]) continue;
for (size_t j = 0; j < E[v].size(); ++j){
int w = E[v][j];
if (w == fa[v]) continue;
int cnt = sube[v] - sube[w] - sone[w];
change(1, 1, n, Ldfn[w], Rdfn[w], pw2[cnt]);
}
int res = ask(1, 1, n, Ldfn[v], Rdfn[v]);
res = (long long)res * inv2[sone[v] + sube[v]] % MOD;
f[u][1] = (((long long)f[u][1] * (res + 1)) + ((long long)f[u][0] * res)) % MOD;
f[u][0] = (f[u][0] + res) % MOD;
}
if (!xtr[u].empty() && subkey[u] - vis[u] >= 2){
for (size_t i = 0; i < E[u].size(); ++i){
int v = E[u][i];
if (v == fa[u]) continue;
change(1, 1, n, Ldfn[v], Rdfn[v], inv2[sone[v] + sube[v]]);
}
vector<int> S;
S.reserve((int)xtr[u].size() * 2 + (int)E[u].size());
for (size_t i = 0; i < xtr[u].size(); ++i){
int a = xtr[u][i].first;
int b = xtr[u][i].second;
S.push_back(Ldfn[a]);
S.push_back(Ldfn[b]);
int x = a, y = b;
if (Ldfn[x] > Ldfn[y]) std::swap(x, y);
insv[y].push_back(x);
}
for (size_t i = 0; i < E[u].size(); ++i){
int v = E[u][i];
if (v == fa[u]) continue;
S.push_back(Ldfn[v]);
}
sort(S.begin(), S.end());
S.erase(unique(S.begin(), S.end()), S.end());
vector<int> vec;
vec.reserve(S.size() * 2);
for (size_t i = 0; i < S.size(); ++i) vec.push_back(S[i]);
for (size_t i = 0; i + 1 < S.size(); ++i){
int l = LCA(nodeAt[S[i]], nodeAt[S[i+1]]);
vec.push_back(Ldfn[l]);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (size_t i = 0; i + 1 < vec.size(); ++i){
int l = LCA(nodeAt[vec[i]], nodeAt[vec[i+1]]);
Vtr[l].push_back(nodeAt[vec[i+1]]);
}
val = 0;
ql = Ldfn[u] + 1;
rootVT = u;
DP4(u);
int sum = 0;
for (size_t i = 0; i < E[u].size(); ++i){
int v = E[u][i];
if (v == fa[u]) continue;
val = ((long long)val + MOD - (long long)sum * ask(1, 1, n, Ldfn[v], Rdfn[v]) % MOD) % MOD;
sum = (sum + ask(1, 1, n, Ldfn[v], Rdfn[v])) % MOD;
}
val = (long long)val * pw2[sube[u]] % MOD;
ans = (ans + (long long)val * dpOut[u]) % MOD;
for (size_t i = 0; i < vec.size(); ++i){
int d = vec[i];
int x = nodeAt[d];
Vtr[x].clear();
insv[x].clear();
}
for (size_t i = 0; i < E[u].size(); ++i){
int v = E[u][i];
if (v == fa[u]) continue;
change(1, 1, n, Ldfn[v], Rdfn[v], pw2[sone[v] + sube[v]]);
}
}
f[u][0] = (long long)f[u][0] * pw2[sube[u]] % MOD;
f[u][1] = (long long)f[u][1] * pw2[sube[u]] % MOD;
if (vis[u] == 1){
f[u][2] = (((long long)f[u][0] + f[u][1] + pw2[sube[u]]) % MOD) * (MOD - 1LL) % MOD;
}
ans = (ans + (long long)((f[u][1] + f[u][2]) % MOD) * dpOut[u]) % MOD;
addPoint(1, 1, n, Ldfn[u], (f[u][1] + f[u][2]) % MOD);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int id;
if (!(cin >> id)) return 0;
cin >> n >> m >> k;
pw2[0] = inv2[0] = 1;
int inv2base = (MOD + 1) / 2;
for (int i = 1; i <= m; ++i){
pw2[i] = (long long)pw2[i-1] * 2 % MOD;
inv2[i] = (long long)inv2[i-1] * inv2base % MOD;
}
for (int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
E[u].push_back(v);
E[v].push_back(u);
}
dfs1(1);
dfs2(1, 1);
for (int i = 1; i <= m; ++i){
int u, v;
cin >> u >> v;
if (dep[u] < dep[v]) std::swap(u, v);
if (LCA(u, v) == v){
toson[v].push_back(u);
tofa[u]++;
sone[jump(u, v)]++;
}else{
int l = LCA(u, v);
xtr[l].push_back(make_pair(u, v));
xtrval[u]++; xtrval[v]++;
}
}
for (int i = 1; i <= k; ++i){
int x; cin >> x;
vis[x] = 1;
}
for (int i = 0; i < (MAXN<<2); ++i) tagv[i] = 1;
DP1(1);
dpOut[1] = 1;
DP2(1);
DP3(1);
cout << ((long long)MOD - ans) % MOD << "\n";
return 0;
}
© 2019 - 2026王码编程 滇ICP备19007937号-1如果您有任何问题，请联系我们 YNO
评论:
请先登录，才能进行评论