Bình luận

• 
  

  -1

  

  Thang12345  đã bình luận lúc 24, Tháng 11, 2025, 8:59

  include <bits/stdc++.h>

  using namespace std; using ll = long long; const ll INF = (1LL<<60);

  int main(){ ios::syncwithstdio(false); cin.tie(nullptr); int n,k,q; if(!(cin>>n>>k>>q)) return 0; // Read all remaining integers from stdin into a vector vector<long long> all; long long x; while(cin>>x) all.push_back(x);

  // We need to reconstruct: either edges-first or specials-first.
  int m = n-1;
  bool ok = false;
  vector<tuple<int,int,int>> edges;
  vector<int> specials;
  vector<pair<vector<int>, vector<int>>> queries; // each: (add list y, remove list x) but in input it's a then y_i, then b then x_i
  // Try edges-first: next 3*m numbers are edges, then k specials, then q queries
  auto try_parse = [&](bool edges_first)->bool{
      edges.clear();
      specials.clear();
      queries.clear();
      size_t idx = 0;
      if(edges_first){
          if((int)all.size() < 3*m + k) return false;
          // edges
          for(int i=0;i&lt;m;i++){
              if(idx+2 >= all.size()) return false;
              int u = (int)all[idx++], v = (int)all[idx++], w = (int)all[idx++];
              if(u&lt;1||u>n||v&lt;1||v>n) return false;
              edges.emplace_back(u-1,v-1,w);
          }
          // specials
          for(int i=0;i&lt;k;i++){
              if(idx >= all.size()) return false;
              int s = (int)all[idx++]; if(s&lt;1||s>n) return false;
              specials.push_back(s-1);
          }
          // queries
          for(int t=0;t&lt;q;t++){
              if(idx >= all.size()) return false;
              int a = (int)all[idx++]; if(a&lt;0||a>200) return false;
              vector<int> add;
              for(int i=0;i&lt;a;i++){
                  if(idx>=all.size()) return false;
                  int y = (int)all[idx++]; if(y&lt;1||y>n) return false;
                  add.push_back(y-1);
              }
              if(idx>=all.size()) return false;
              int b = (int)all[idx++]; if(b&lt;0||b>200) return false;
              vector<int> rem;
              for(int i=0;i&lt;b;i++){
                  if(idx>=all.size()) return false;
                  int z = (int)all[idx++]; if(z&lt;1||z>n) return false;
                  rem.push_back(z-1);
              }
              queries.emplace_back(add, rem);
          }
          if(idx != all.size()) return false;
          return true;
      } else {
          // specials first
          if((int)all.size() < k + 3*m) return false;
          for(int i=0;i&lt;k;i++){
              if(idx >= all.size()) return false;
              int s = (int)all[idx++]; if(s&lt;1||s>n) return false;
              specials.push_back(s-1);
          }
          for(int i=0;i&lt;m;i++){
              if(idx+2 >= all.size()) return false;
              int u = (int)all[idx++], v = (int)all[idx++], w = (int)all[idx++];
              if(u&lt;1||u>n||v&lt;1||v>n) return false;
              edges.emplace_back(u-1,v-1,w);
          }
          for(int t=0;t&lt;q;t++){
              if(idx >= all.size()) return false;
              int a = (int)all[idx++]; if(a&lt;0||a>200) return false;
              vector<int> add;
              for(int i=0;i&lt;a;i++){
                  if(idx>=all.size()) return false;
                  int y = (int)all[idx++]; if(y&lt;1||y>n) return false;
                  add.push_back(y-1);
              }
              if(idx>=all.size()) return false;
              int b = (int)all[idx++]; if(b&lt;0||b>200) return false;
              vector<int> rem;
              for(int i=0;i&lt;b;i++){
                  if(idx>=all.size()) return false;
                  int z = (int)all[idx++]; if(z&lt;1||z>n) return false;
                  rem.push_back(z-1);
              }
              queries.emplace_back(add, rem);
          }
          if(idx != all.size()) return false;
          return true;
      }
  };
  
  if(try_parse(true)) ok = true;
  else if(try_parse(false)) ok = true;
  if(!ok){
      cerr << "Không thể phân tích input. Hãy kiểm tra định dạng.\n";
      return 0;
  }
  
  // Build adjacency
  vector<vector<pair<int,int>>> g(n);
  for(auto &e: edges){
      int u,v,w; tie(u,v,w)=e;
      g[u].push_back({v,w});
      g[v].push_back({u,w});
  }
  
  // current special set mask
  vector<char> isSpecial(n, 0);
  for(int s: specials) isSpecial[s]=1;
  
  auto compute_sum = [&]()->long long{
      // multi-source dijkstra
      vector&lt;long long> dist(n, INF);
      priority_queue&lt;pair&lt;long long,int>, vector&lt;pair&lt;long long,int>>, greater&lt;pair&lt;long long,int>>> pq;
      for(int i=0;i&lt;n;i++) if(isSpecial[i]){
          dist[i]=0; pq.push({0,i});
      }
      while(!pq.empty()){
          auto [d,u]=pq.top(); pq.pop();
          if(d!=dist[u]) continue;
          for(auto [v,w]: g[u]){
              if(dist[v] > d + w){
                  dist[v] = d + w;
                  pq.push({dist[v], v});
              }
          }
      }
      long long sum=0;
      for(int i=0;i&lt;n;i++){
          // problem guarantees at least one special in every state
          sum += dist[i];
      }
      return sum;
  };
  
  // Output initial
  cout << compute_sum() << "\n";
  // Process queries in original order
  for(auto &qr : queries){
      auto add = qr.first;
      auto rem = qr.second;
      // according to original problem statement: queries are "xóa ... khỏi tập" then "thêm ... vào tập"
      // but in example input, after edges there's 0 then 1 2 => that matched a=0 then b=1 with x=2 (i.e., remove 2)
      // Original problem wording earlier: "một truy vấn thay đổi các đỉnh đặc biệt, mời truy vấn sẽ xóa a đỉnh y1..ya khỏi tập, sau đó thêm b đỉnh z1..zb vào tập"
      // Our parsing stored (add, rem) as (y list, x list) for the order we parsed. To be robust, assume parsed pair is (add, rem) where add = y_i (to add), rem = x_i (to remove).
      // So apply removals first then additions according to problem statement:
      for(int v: rem) isSpecial[v]=0;
      for(int v: add) isSpecial[v]=1;
      cout << compute_sum() << "\n";
  }
  
  return 0;
  

  }