fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct DSU {
  5.     vector<int> p, r;
  6.     DSU(int n=0){ init(n); }
  7.     void init(int n){ p.resize(n); r.assign(n,0); iota(p.begin(), p.end(), 0); }
  8.     int find(int x){ return p[x]==x ? x : p[x]=find(p[x]); }
  9.     bool unite(int a,int b){
  10.         a=find(a); b=find(b);
  11.         if(a==b) return false;
  12.         if(r[a]<r[b]) swap(a,b);
  13.         p[b]=a; if(r[a]==r[b]) r[a]++;
  14.         return true;
  15.     }
  16. };
  17.  
  18. struct Edge{ int u,v; long long w; };
  19.  
  20. int main(){
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(nullptr);
  23.  
  24.     int n, m, q;
  25.     if(!(cin >> n >> m >> q)) return 0;
  26.  
  27.     vector<Edge> E(m);
  28.     for(int i=0;i<m;i++){
  29.         int u,v; long long w;
  30.         cin >> u >> v >> w;
  31.         E[i] = {u,v,w};
  32.     }
  33.  
  34.     // 1) Kruskal -> MST T
  35.     sort(E.begin(), E.end(), [](const Edge& a, const Edge& b){ return a.w < b.w; });
  36.     DSU dsu(n);
  37.     vector<vector<pair<int,long long>>> g(n);        // !!! long long weight
  38.     long long W = 0;
  39.     int used = 0;
  40.     for(const auto &e : E){
  41.         if(dsu.unite(e.u, e.v)){
  42.             W += e.w;
  43.             g[e.u].push_back({e.v, e.w});
  44.             g[e.v].push_back({e.u, e.w});
  45.             if(++used == n-1) break;
  46.         }
  47.     }
  48.     // giả sử đồ thị ban đầu liên thông
  49.  
  50.     // 2) Euler tour + RMQ cho LCA O(1)
  51.     vector<int> tin(n,-1), depth(n,0), parent(n,-1);
  52.     vector<long long> dist(n,0);
  53.     vector<int> first(n,-1), euler;
  54.     euler.reserve(2*n);
  55.  
  56.     int timerTin = 0;
  57.  
  58.     // iterative DFS để tránh stack overflow
  59.     vector<pair<int,int>> st; // (v, next_child_idx)
  60.     st.push_back({0,0});
  61.     parent[0] = -1;
  62.     tin[0] = timerTin++;
  63.     first[0] = (int)euler.size();
  64.     euler.push_back(0);
  65.  
  66.     while(!st.empty()){
  67.         int v = st.back().first;
  68.         int &i = st.back().second;
  69.         if(i < (int)g[v].size()){
  70.             auto [to, w] = g[v][i++];
  71.             if(to == parent[v]) continue;
  72.             parent[to] = v;
  73.             depth[to] = depth[v] + 1;
  74.             dist[to]  = dist[v] + w;
  75.             tin[to]   = timerTin++;
  76.             first[to] = (int)euler.size();
  77.             euler.push_back(to);
  78.             st.push_back({to,0});
  79.         }else{
  80.             st.pop_back();
  81.             if(!st.empty()){
  82.                 int p = st.back().first;
  83.                 euler.push_back(p);
  84.             }
  85.         }
  86.     }
  87.  
  88.     int M = (int)euler.size();
  89.     vector<int> lg(M+1,0);
  90.     for(int i=2;i<=M;i++) lg[i] = lg[i/2]+1;
  91.     int K = lg[M]+1;
  92.  
  93.     vector<vector<int>> stmin(K, vector<int>(M));
  94.     stmin[0] = euler;
  95.     auto better = [&](int a,int b){ return depth[a] < depth[b] ? a : b; };
  96.     for(int k=1;k<K;k++){
  97.         int len = 1<<(k-1);
  98.         for(int i=0;i + (1<<k) <= M; i++){
  99.             stmin[k][i] = better(stmin[k-1][i], stmin[k-1][i+len]);
  100.         }
  101.     }
  102.     auto lca = [&](int u,int v){
  103.         int L = first[u], R = first[v];
  104.         if(L>R) swap(L,R);
  105.         int k = lg[R-L+1];
  106.         int a = stmin[k][L];
  107.         int b = stmin[k][R-(1<<k)+1];
  108.         return better(a,b);
  109.     };
  110.     auto dist_uv = [&](int u,int v)->long long{
  111.         int w = lca(u,v);
  112.         return dist[u] + dist[v] - 2LL*dist[w];
  113.     };
  114.  
  115.     // 3) Mo trên dãy đỉnh [0..n-1]
  116.     struct Query{ int l,r,idx; };
  117.     vector<Query> Q(q);
  118.     for(int i=0;i<q;i++){
  119.         int L,R; cin >> L >> R;
  120.         Q[i] = {L,R,i};
  121.     }
  122.     int B = max(1, (int)sqrt(n));
  123.     sort(Q.begin(), Q.end(), [&](const Query& A, const Query& BQ){
  124.         int ba = A.l / B, bb = BQ.l / B;
  125.         if(ba != bb) return ba < bb;
  126.         if(ba & 1) return A.r > BQ.r;
  127.         return A.r < BQ.r;
  128.     });
  129.  
  130.     set<pair<int,int>> S; // (tin, node)
  131.     vector<char> in(n,0);
  132.     long long P = 0;      // tổng dist giữa các đỉnh kề nhau theo thứ tự tin (chu trình)
  133.  
  134.     auto add_node = [&](int x){
  135.         if(in[x]) return;
  136.         in[x] = 1;
  137.         if(S.empty()){ S.insert({tin[x],x}); return; }
  138.         auto it = S.lower_bound({tin[x],x});
  139.         auto itNext = (it == S.end() ? S.begin() : it);
  140.         auto itPrev = (it == S.begin() ? prev(S.end()) : prev(it));
  141.         int a = itPrev->second, b = itNext->second;
  142.         P += dist_uv(a,x) + dist_uv(x,b) - dist_uv(a,b);
  143.         S.insert({tin[x],x});
  144.     };
  145.     auto remove_node = [&](int x){
  146.         if(!in[x]) return;
  147.         in[x] = 0;
  148.         if(S.size()==1){ S.clear(); return; }
  149.         auto it = S.find({tin[x],x});
  150.         auto itNext = next(it); if(itNext==S.end()) itNext = S.begin();
  151.         auto itPrev = (it==S.begin()? prev(S.end()) : prev(it));
  152.         int a = itPrev->second, b = itNext->second;
  153.         P -= dist_uv(a,x) + dist_uv(x,b) - dist_uv(a,b);
  154.         S.erase(it);
  155.     };
  156.  
  157.     vector<long long> ans(q);
  158.     int curL = 0, curR = -1;
  159.     for(const auto &qq : Q){
  160.         while(curL > qq.l) add_node(--curL);
  161.         while(curR < qq.r) add_node(++curR);
  162.         while(curL < qq.l) remove_node(curL++);
  163.         while(curR > qq.r) remove_node(curR--);
  164.         ans[qq.idx] = W - P/2; // cây Steiner = P/2
  165.     }
  166.  
  167.     for(int i=0;i<q;i++) cout << ans[i] << '\n';
  168.     return 0;
  169. }
  170.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
7 7 4
0 3 2
6 4 3
1 4 5
3 2 4
5 2 3
4 0 1
1 3 1
0 1
5 6
2 3
4 5
stdout 
11
1
10
4
https://ideone.com/CJ3p0q
language:
C++14 (gcc 8.3)
created:
15 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!