fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<long long , int>
  10. #define lll pair<long long , pair<long long , long long>>
  11. #define lii pair<long long , pair<long long , int>>
  12. #define iii pair<int , pair<int , int>>
  13. #define iiii pair<pair<int , int> , pair<int , int>>
  14. #define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
  15. #define li pair<long long , int>
  16. #define db long double
  17. #define onBit(mask , i) (mask | (1 << i))
  18. #define offBit(mask , i) (mask & (~(1 << i)))
  19.  
  20. const int N = 1e5 + 7;
  21. int n , cnt = 0 , q;
  22. vector<pair<int , int>> a[N];
  23. int tin[N] , h[N] , up[21][N];
  24. long long Val[N];
  25. bool vit[N];
  26.  
  27. void dfs(int u , int p){
  28.     tin[u] = ++cnt;
  29.     for (auto &c : a[u]) if (c.fi != p){
  30.         int v = c.fi;
  31.         h[v] = h[u] + 1;
  32.         Val[v] = Val[u] + c.se;
  33.         up[0][v] = u;
  34.  
  35.         dfs(v , u);
  36.     }
  37. }
  38.  
  39. void inp(){
  40.     cin >> n >> q;
  41.     for (int i = 1 ; i < n ; ++i){
  42.         int u , v;
  43.         long long w;
  44.         cin >> u >> v >> w;
  45.         a[u].push_back({v , w});
  46.         a[v].push_back({u , w});
  47.     }
  48.  
  49.     h[1] = 1;
  50.     dfs(1 , 0);
  51.  
  52.     for (int j = 1 ; j <= 17 ; ++j){
  53.         for (int i = 1 ; i <= n ; ++i){
  54.             up[j][i] = up[j - 1][up[j - 1][i]];
  55.         }
  56.     }
  57. }
  58.  
  59. int lca(int u , int v){
  60.     if (h[u] < h[v]) swap(u , v);
  61.  
  62.     for (int i = _LOG2(h[u]) ; i >= 0 ; --i) if(h[up[i][u]] >= h[v]){
  63.         u = up[i][u];
  64.     }
  65.  
  66.     if (u == v) return u;
  67.  
  68.     for (int i = _LOG2(h[u]) ; i >= 0 ; --i) if (up[i][u] != up[i][v]){
  69.         u = up[i][u];
  70.         v = up[i][v];
  71.     }
  72.  
  73.     return up[0][u];
  74. }
  75.  
  76. long long d(int u , int v){
  77. //    if (u == 0 || v == 0) return 0;
  78. //    if (u == n + 1 || v == n + 1) return 0;
  79.     int p = lca(u , v);
  80.  
  81.     return Val[u] + Val[v] - (1LL * 2) * Val[p];
  82. }
  83.  
  84. long long Cnt = 0;
  85. set<pair<int , int>> st;
  86.  
  87. void Push(int id , int in){
  88.     st.insert({in , id});
  89.     if (st.size() == 1) return;
  90.     auto it = st.lower_bound({in , id});
  91.     auto it2 = it;
  92.     ++it2;
  93.  
  94.     if (it == st.begin()){
  95.         auto it1 = st.rbegin();
  96.  
  97.         if (st.size() > 2) Cnt -= d(it1->se , it2->se);
  98.         Cnt += d(it->se , it2->se);
  99.         Cnt += d(it->se , it1->se);
  100.         return;
  101.     }
  102.     if (it2 == st.end()){
  103.         it2 = st.begin();
  104.         auto it1 = it;
  105.         --it1;
  106.  
  107.         if (st.size() > 2) Cnt -= d(it1->se , it2->se);
  108.         Cnt += d(it->se , it2->se);
  109.         Cnt += d(it->se , it1->se);
  110.         return;
  111.     }
  112.  
  113.     auto it1 = it;
  114.     --it1;
  115.     Cnt -= d(it1->se , it2->se);
  116.     Cnt += d(it->se , it2->se);
  117.     Cnt += d(it->se , it1->se);
  118. }
  119.  
  120. void Erase(int id , int in){
  121.     auto it = st.lower_bound({in , id});
  122.     if (st.size() == 1){
  123.         st.erase(it);
  124.         return;
  125.     }
  126.     auto it2 = it;
  127.     ++it2;
  128.  
  129.     if (it == st.begin()){
  130.         auto it1 = st.rbegin();
  131.  
  132.         if (st.size() > 2) Cnt += d(it1->se , it2->se);
  133.         Cnt -= d(it->se , it2->se);
  134.         Cnt -= d(it->se , it1->se);
  135.         st.erase(it);
  136.         return;
  137.     }
  138.     if (it2 == st.end()){
  139.         it2 = st.begin();
  140.         auto it1 = it;
  141.         --it1;
  142.  
  143.         if (st.size() > 2) Cnt += d(it1->se , it2->se);
  144.         Cnt -= d(it->se , it2->se);
  145.         Cnt -= d(it->se , it1->se);
  146.         st.erase(it);
  147.         return;
  148.     }
  149.  
  150.     auto it1 = it;
  151.     --it1;
  152.     Cnt += d(it1->se , it2->se);
  153.     Cnt -= d(it->se , it2->se);
  154.     Cnt -= d(it->se , it1->se);
  155.  
  156.     st.erase(it);
  157. }
  158.  
  159. void solve(){
  160.     while (q--){
  161.         int u;
  162.         cin >> u;
  163.         if (!vit[u]){
  164.             vit[u] = 1;
  165.             Push(u , tin[u]);
  166.         }
  167.         else{
  168.             vit[u] = 0;
  169.             Erase(u , tin[u]);
  170.         }
  171.  
  172.         cout << Cnt << '\n';
  173.     }
  174. }
  175.  
  176. int main(){
  177. //    freopen("difmax.inp" , "r" , stdin);
  178. //    freopen("difmax.out" , "w" , stdout);
  179.     faster;
  180.     inp();
  181.     solve();
  182.     return 0;
  183. }
  184.  
Success #stdin #stdout 0.01s 8832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5nk5Rs
language:
C++14 (gcc 8.3)
created:
4 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!