DAY0(2024.11.15)
T2 GYM104787M
首先定义一个副本连通块是只经过编号 \(> n\) 的节点形成的连通块。不难发现一个副本连通块（绿色）会连接着一些编号 \(< n\) 的叶子，然后与原图联通，并且与原图相同部分组成一个对称的连通块。就像下面的图一样：
然后假如有 \(lf\) 个叶子（蓝色节点），其实就是要割掉 \(lf - 1\) 条边，且删掉后的图连通。于是把那些删除的边全部翻到原树上，不难发现一个方案合法当且仅当在原树上每个连通块中都有一个叶子。于是直接 \(\mathrm {DP}\) 即可。
qwq
#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
using namespace std;
const int N = 5000 + 10;
const ll mod = 998244353;
struct edge{
int v, next;
}edges[N << 1];
int head[N], idx;
int n;
bool chosen[N], vis[N];
ll f[N], g[N], pw2[N];
void add_edge(int u, int v){
edges[++idx] = {v, head[u]};
head[u] = idx;
}
int lfcnt;
void dfs(int u, int fa){
//cout << u << " " << fa << "\n";
if(!chosen[u]){lfcnt++; f[u] = 1; g[u] = 0; return;}
f[u] = 0; g[u] = 1; vis[u] = 1;
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v; if(v == fa) continue;
dfs(v, u);
f[u] = (f[u] * (g[v] + f[v]) % mod + f[v] * g[u] % mod) % mod;
g[u] = (g[u] * (g[v] + f[v])) % mod;
//cout << u << " " << v << " " << f[u] << " " << g[u] << "\n";
}
}
signed main(){
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n; pw2[0] = 1;
for(int i = 1; i <= n; i++) pw2[i] = 2ll * pw2[i - 1] % mod;
for(int i = 1; i < n; i++){
int x, y; cin >> x >> y;
add_edge(x, y); add_edge(y, x);
}
for(int i = 1; i < n; i++){
int x; cin >> x; chosen[x] = 1;
for(int u = 1; u <= n; u++) vis[u] = 0, f[u] = g[u] = 0;
ll ans = 1;
for(int u = 1; u <= n; u++) if(!vis[u] && chosen[u]) lfcnt = 0, dfs(u, 0), ans = (ans * f[u] % mod * pw2[lfcnt - 1] % mod) % mod;
cout << ans % mod << "\n";
}
return 0;
}