Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- #define pb push_back
- #define vi vector<int>
- #define ii pair<int,int>
- #define iii pair<int, ii>
- #define iiii pair<ii, ii>
- #define Task "test"
- #define all(x) x.begin(),x.end()
- using namespace std;
- const int N = 3e5+5;
- const int inf = 1e9+9;
- const int mod = 1e9+7;
- const int base = 33;
- void readfile(){
- if (fopen(Task".inp","r")){
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- }
- int n, m, c[205];
- vector<int> g[205];
- int dp[205][3];
- bool is_edge[205];
- void reset(){
- for(int i=1; i<=n; i++) g[i].clear();
- }
- void dfs(int u, int par){
- int sum1 = 0, sum2 = 0;
- for(auto v : g[u]){
- if (v!=par) dfs(v,u);
- sum1 += dp[v][2];
- if (is_edge[v]) sum2 += max(dp[v][1],dp[v][2]);
- else sum2 += dp[v][2];
- }
- if (is_edge[u]) dp[u][1] = sum1 + c[u];
- else dp[u][1] = sum1;
- dp[u][2] = sum2;
- }
- void solve(){
- cin >> n >> m;
- for(int i=0; i<n; i++) cin >> c[i];
- reset();
- for(int i=1; i<=m; i++){
- int u, v; cin >> u >> v;
- g[u].pb(v);
- g[v].pb(u);
- }
- int t; cin >> t;
- while (t--){
- int k; cin >> k;
- memset(is_edge, false, sizeof is_edge);
- for(int i=1; i<=k; i++){
- int node; cin >> node;
- is_edge[node] = true;
- }
- int ans = 0;
- for(int i=0; i<n; i++){
- dp[i][1] = dp[i][2] = 0;
- }
- for(int i=0; i<n; i++){
- if (is_edge[i] && dp[i][1]==0){
- dfs(i,i);
- ans += max(dp[i][1],dp[i][2]);
- }
- }
- cout << ans << '\n';
- }
- }
- void proc(){
- int q;
- cin >> q;
- //q=1;
- while (q--){
- solve();
- cout << '\n';
- }
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment