fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct DSU {
  5.     int n;
  6.     vector<int> p, r;
  7.     DSU(int n=0): n(n), p(n), r(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. const int MAXN = 200000 + 5; // just a soft cap; we will use vectors anyway
  19.  
  20. int n, m, q;
  21.  
  22. vector<vector<pair<int,long long>>> g; // MST adjacency
  23. long long W_MST = 0;
  24.  
  25. // LCA
  26. int LOGN;
  27. vector<int> tin, tout, depth;
  28. vector<vector<int>> up;
  29. vector<long long> distRoot;
  30. int timerDFS = 0;
  31.  
  32. void dfs(int u, int p){
  33.     tin[u] = ++timerDFS;
  34.     up[u][0] = (p==-1?u:p);
  35.     for(int j=1;j<LOGN;j++) up[u][j] = up[ up[u][j-1] ][j-1];
  36.     for(auto [v,w] : g[u]){
  37.         if(v==p) continue;
  38.         depth[v] = depth[u] + 1;
  39.         distRoot[v] = distRoot[u] + w;
  40.         dfs(v,u);
  41.     }
  42.     tout[u] = ++timerDFS;
  43. }
  44. bool is_anc(int u,int v){ // u is ancestor of v?
  45.     return tin[u]<=tin[v] && tout[v]<=tout[u];
  46. }
  47. int lca(int u,int v){
  48.     if(is_anc(u,v)) return u;
  49.     if(is_anc(v,u)) return v;
  50.     for(int j=LOGN-1;j>=0;j--){
  51.         int uu = up[u][j];
  52.         if(!is_anc(uu,v)) u = uu;
  53.     }
  54.     return up[u][0];
  55. }
  56. inline long long dist_uv(int u,int v){
  57.     int w = lca(u,v);
  58.     return distRoot[u] + distRoot[v] - 2LL*distRoot[w];
  59. }
  60.  
  61. // Mo's
  62. struct Query{
  63.     int L, R, idx, block;
  64. };
  65. int B;
  66.  
  67. struct ByMo {
  68.     bool operator()(const Query& a, const Query& b) const {
  69.         if(a.block != b.block) return a.block < b.block;
  70.         if(a.block & 1) return a.R > b.R;
  71.         return a.R < b.R;
  72.     }
  73. };
  74.  
  75. // ordered set over Euler time
  76. set<pair<int,int>> S; // (tin[u], u)
  77. vector<int> inSet;
  78. long long sumDist = 0;
  79.  
  80. inline void add_contrib(int a,int b, long long sign){ // sign = +1 or -1
  81.     if(a==b) return;
  82.     sumDist += sign * dist_uv(a,b);
  83. }
  84.  
  85. void insert_vertex(int u){
  86.     if(S.empty()){
  87.         S.insert({tin[u], u});
  88.         inSet[u]=1;
  89.         return;
  90.     }
  91.     auto key = make_pair(tin[u], u);
  92.     auto it = S.lower_bound(key);
  93.     auto itNext = (it == S.end() ? S.begin() : it);
  94.     auto itPrev = (it == S.begin() ? prev(S.end()) : prev(it));
  95.     int a = itPrev->second;
  96.     int b = itNext->second;
  97.     // add dist(a,u) + dist(u,b) - dist(a,b)
  98.     add_contrib(a, u, +1);
  99.     add_contrib(u, b, +1);
  100.     add_contrib(a, b, -1);
  101.     S.insert(key);
  102.     inSet[u]=1;
  103. }
  104.  
  105. void erase_vertex(int u){
  106.     if(S.size()==1){
  107.         S.erase({tin[u],u});
  108.         inSet[u]=0;
  109.         return;
  110.     }
  111.     auto it = S.find({tin[u],u});
  112.     auto itNext = next(it); if(itNext==S.end()) itNext = S.begin();
  113.     auto itPrev = (it==S.begin() ? prev(S.end()) : prev(it));
  114.     int a = itPrev->second;
  115.     int b = itNext->second;
  116.     // remove dist(a,u) + dist(u,b) - dist(a,b)
  117.     add_contrib(a, u, -1);
  118.     add_contrib(u, b, -1);
  119.     add_contrib(a, b, +1);
  120.     S.erase(it);
  121.     inSet[u]=0;
  122. }
  123.  
  124. inline void add_pos(int x){ if(!inSet[x]) insert_vertex(x); }
  125. inline void rem_pos(int x){ if(inSet[x]) erase_vertex(x); }
  126.  
  127. int main(){
  128.     ios::sync_with_stdio(false);
  129.     cin.tie(nullptr);
  130.  
  131.     if(!(cin>>n>>m>>q)) return 0;
  132.  
  133.     struct Edge{int u,v; long long w;};
  134.     vector<Edge> edges(m);
  135.     for(int i=0;i<m;i++){
  136.         int u,v; long long w;
  137.         cin>>u>>v>>w;
  138.         edges[i]={u,v,w};
  139.     }
  140.  
  141.     // Kruskal -> MST
  142.     sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){
  143.         return a.w < b.w;
  144.     });
  145.     DSU dsu(n);
  146.     g.assign(n, {});
  147.     int cnt=0;
  148.     for(auto &e: edges){
  149.         if(dsu.unite(e.u, e.v)){
  150.             W_MST += e.w;
  151.             g[e.u].push_back({e.v, e.w});
  152.             g[e.v].push_back({e.u, e.w});
  153.             cnt++;
  154.             if(cnt==n-1) break;
  155.         }
  156.     }
  157.     // (Nếu đồ thị không liên thông, phần lớn đề đảm bảo không xảy ra)
  158.  
  159.     // LCA precompute
  160.     LOGN = 1;
  161.     while((1<<LOGN) <= n) LOGN++;
  162.     tin.assign(n,0); tout.assign(n,0); depth.assign(n,0);
  163.     up.assign(n, vector<int>(LOGN));
  164.     distRoot.assign(n,0);
  165.  
  166.     dfs(0,-1);
  167.  
  168.     // Read queries
  169.     vector<Query> Q(q);
  170.     B = max(1, (int)(sqrt(n) + 1));
  171.     for(int i=0;i<q;i++){
  172.         int L,R; cin>>L>>R;
  173.         Q[i] = {L, R, i, L / B};
  174.     }
  175.     sort(Q.begin(), Q.end(), ByMo());
  176.  
  177.     inSet.assign(n, 0);
  178.     long long curSum = 0;
  179.     sumDist = 0;
  180.     S.clear();
  181.  
  182.     vector<long long> ans(q, 0);
  183.  
  184.     int curL = 0, curR = -1;
  185.     for(auto &qq: Q){
  186.         while(curL > qq.L){ --curL; add_pos(curL); }
  187.         while(curR < qq.R){ ++curR; add_pos(curR); }
  188.         while(curL < qq.L){ rem_pos(curL); ++curL; }
  189.         while(curR > qq.R){ rem_pos(curR); --curR; }
  190.  
  191.         long long virtLen = sumDist / 2; // length of virtual tree covering [L..R]
  192.         ans[qq.idx] = W_MST - virtLen;
  193.     }
  194.  
  195.     for(int i=0;i<q;i++){
  196.         cout << ans[i] << "\n";
  197.     }
  198.     return 0;
  199. }
  200.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5 5 3
0 1 2
0 2 5
0 3 6
1 2 3
2 4 3
1 1
1 4
3 4
stdout 
14
0
0
https://ideone.com/2UJWhU
language:
C++14 (clang 8.0)
created:
14 hours 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!