#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3010;
int n,m,k[N][N],ans,dp[N][N],vis[N][N],a[N];
vector<int> e[N];
bool dfs(int time,int u){
//cout<<time<<" "<<u<<endl;
if(k[time][u]) return 0;
if(time == m) return 1;
if(vis[time][u]) return dp[time][u];
vis[time][u] = 1;
if(dfs(time+1,u))
return dp[time][u] = 1;
for(auto ed : e[u]){
if(dfs(time+1,ed))
return dp[time][u] = 1;
}
return dp[time][u] = 0;
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#ifdef ONLINE_JUDGE
freopen("survive.in ","r",stdin);
freopen("survive.out","w",stdout);
#endif
cin >> n >> m;
for(int i = 1;i <= n;i ++){
cin >> a[i];
}
for(int i = 1;i < n;i ++){
int u,v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i = 1;i <= m;i ++){
int x,y;
cin >> x;
for(int j = 1;j <= x;j ++){
cin >> y;
k[i][y] = 1;
}
}
for(int i = 1;i <= n;i ++){
//cout << i << ": "<<endl;
if(a[i] && dfs(0,i)){
ans += a[i];
}
}
cout << ans;
return 0;
}
这是一份理应TLE62分的代码
but
会WA0
经本地测验
单独样例正确
如图
机测：
自测：
