HoangMinhNguyen

Untitled

Jun 27th, 2022
27
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define pb push_back
  5. #define vi vector<int>
  6. #define ii pair<int,int>
  7. #define iii pair<int, ii>
  8. #define iiii pair<ii, ii>
  9. #define Task "test"
  10. #define all(x) x.begin(),x.end()
  11.  
  12. using namespace std;
  13. const int N = 3e5+5;
  14. const int inf = 1e9+9;
  15. const int mod = 1e9+7;
  16. const int base = 33;
  17.  
  18. void readfile(){
  19.     if (fopen(Task".inp","r")){
  20.         freopen(Task".inp","r",stdin);
  21.         //freopen(Task".out","w",stdout);
  22.     }
  23. }
  24.  
  25. int n, m, c[205];
  26. vector<int> g[205];
  27. int dp[205][3];
  28. bool is_edge[205];
  29.  
  30. void reset(){
  31.     for(int i=1; i<=n; i++) g[i].clear();
  32. }
  33.  
  34. void dfs(int u, int par){
  35.     int sum1 = 0, sum2 = 0;
  36.     for(auto v : g[u]){
  37.         if (v!=par) dfs(v,u);
  38.         sum1 += dp[v][2];
  39.         if (is_edge[v]) sum2 += max(dp[v][1],dp[v][2]);
  40.         else sum2 += dp[v][2];
  41.     }
  42.     if (is_edge[u]) dp[u][1] = sum1 + c[u];
  43.     else dp[u][1] = sum1;
  44.     dp[u][2] = sum2;
  45. }
  46.  
  47. void solve(){
  48.     cin >> n >> m;
  49.     for(int i=0; i<n; i++) cin >> c[i];
  50.     reset();
  51.     for(int i=1; i<=m; i++){
  52.         int u, v; cin >> u >> v;
  53.         g[u].pb(v);
  54.         g[v].pb(u);
  55.     }
  56.     int t; cin >> t;
  57.     while (t--){
  58.         int k; cin >> k;
  59.         memset(is_edge, false, sizeof is_edge);
  60.         for(int i=1; i<=k; i++){
  61.             int node; cin >> node;
  62.             is_edge[node] = true;
  63.         }
  64.         int ans = 0;
  65.         for(int i=0; i<n; i++){
  66.             dp[i][1] = dp[i][2] = 0;
  67.         }
  68.         for(int i=0; i<n; i++){
  69.             if (is_edge[i] && dp[i][1]==0){
  70.                 dfs(i,i);
  71.                 ans += max(dp[i][1],dp[i][2]);
  72.             }
  73.         }
  74.         cout << ans << '\n';
  75.     }
  76. }
  77.  
  78. void proc(){
  79.     int q;
  80.     cin >> q;
  81.     //q=1;
  82.     while (q--){
  83.         solve();
  84.         cout << '\n';
  85.     }
  86. }
  87.  
  88. signed main()
  89. {
  90.     readfile();
  91.     proc();
  92.     return 0;
  93. }
  94.  
Advertisement
Add Comment
Please, Sign In to add comment