fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // define
  5.  
  6. #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
  7. #define ll long long
  8. #define ii pair <int , int>
  9. #define iii pair <int , ii>
  10. #define se second
  11. #define fi first
  12. #define all(v) (v).begin() , (v).end()
  13. #define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin())
  14. #define bit(x,i) (((x) >> (i)) & 1LL)
  15. #define flip(x,i) ((x) ^ (1LL << (i)))
  16. #define ms(d,x) memset(d , x , sizeof(d))
  17. #define exist __exist
  18. #define ends __ends
  19. #define visit visited
  20. #define left __left
  21. #define right __right
  22. #define sitingfake 1
  23. #define orz 1
  24. //constant
  25.  
  26. const long long mod = 1e9 + 7;
  27. const long long linf = 4557430888798830399LL;
  28. const long long nlinf = -4485090715960753727LL;
  29. const int inf = 1061109567;
  30. const int ninf = -1044266559;
  31. const int dx[] = {0 , -1 , 0 , 1};
  32. const int dy[] = {-1 , 0 , 1 , 0};
  33.  
  34. template<typename T> bool maximize(T &a, const T &b)
  35. {
  36.     if(a < b) {a = b; return 1;}
  37.     return 0;
  38. }
  39.  
  40. template<typename T> bool minimize(T &a, const T &b)
  41. {
  42.     if(a > b) {a = b; return 1;}
  43.     return 0;
  44. }
  45.  
  46. void Plus(ll & a ,ll b)
  47. {
  48.     b %= mod;
  49.     a += b;
  50.     if(a < 0) a += mod;
  51.     a %= mod;
  52.     return;
  53. }
  54.  
  55. void Mul(ll & a, ll b)
  56. {
  57.     (a *= (b % mod)) %= mod;
  58.     return;
  59. }
  60.  
  61. //code
  62. const int maxn = 3e5 + 5;
  63.  
  64. int n , q;
  65.  
  66. bool isc[maxn];
  67.  
  68. int par[maxn];
  69.  
  70. int in[maxn] , out[maxn] , depth[maxn];
  71.  
  72. int timer;
  73.  
  74. ii arr[maxn * 2][20];
  75.  
  76. vector <ii> a[maxn];
  77.  
  78. ll val[maxn] , SumW[maxn];
  79.  
  80. vector <ll> sumChild[maxn];
  81.  
  82. int numchild[maxn] , pos[maxn];
  83.  
  84. ll stateOn[maxn];
  85. int  state[maxn] , sz[maxn];
  86.  
  87. ll ans;
  88.  
  89. void dfs(int u , int p)
  90. {
  91.     in[u] = ++timer;
  92.     arr[timer][0] = ii(depth[u] , u);
  93.     for(ii i : a[u])
  94.     {
  95.         int v = i.fi;
  96.         ll w = i.se;
  97.         if(v != p)
  98.         {
  99.             depth[v] = depth[u] + 1;
  100.             val[v] = val[u] + w;
  101.             dfs(v , u);
  102.             arr[++timer][0] = ii(depth[u] , u);
  103.         }
  104.     }
  105.     out[u] = timer;
  106. }
  107.  
  108. void BuildLca()
  109. {
  110.  
  111.     for(int j = 1; (1 << j) <= timer ; j++)
  112.     {
  113.         for(int i = 1; i + (1 << j) - 1 <= timer ; i++)
  114.         {
  115.             arr[i][j] = min(arr[i][j-1] , arr[i + (1 << (j - 1))][j-1]);
  116.         }
  117.     }
  118. }
  119.  
  120. inline int lca(int u , int v)
  121. {
  122.     int l = min(in[u] , in[v]) , r = max(in[u] , in[v]);
  123.  
  124.     int k = __lg(r - l + 1);
  125.  
  126.     ii ans = min(arr[l][k] , arr[r - (1 << k) + 1][k]);
  127.  
  128.     return ans.se;
  129. }
  130.  
  131. inline ll dist(int u ,int v)
  132. {
  133.     return val[u] + val[v] - 2 * val[lca(u ,v)];
  134. }
  135.  
  136. void dfscount(int u , int p)
  137. {
  138.     sz[u] = 1;
  139.     for(ii i : a[u])
  140.     {
  141.         if(!isc[i.fi] && i.fi != p)
  142.         {
  143.             dfscount(i.fi , u);
  144.             sz[u] += sz[i.fi];
  145.         }
  146.     }
  147. }
  148.  
  149. int Centroid(int u , int p , int Size)
  150. {
  151.     for(ii i : a[u])
  152.     {
  153.         int v = i.fi;
  154.         if(v != p && !isc[v] && sz[v] > Size / 2)
  155.         {
  156.             return Centroid(v , u , Size);
  157.         }
  158.     }
  159.     return u;
  160. }
  161. void cd(int u , int pre)
  162. {
  163.     dfscount(u , -1);
  164.     int c = Centroid(u , -1 , sz[u]);
  165.     isc[c] = 1;
  166.     par[c] = pre;
  167.     pos[c] = numchild[pre]++;
  168.     //cout << c << " " << pre << endl;
  169.     for(ii i : a[c])
  170.     {
  171.         int v = i.fi;
  172.         if(!isc[v])
  173.         {
  174.             cd(v , c);
  175.         }
  176.     }
  177. }
  178.  
  179. void Add(int u)
  180. {
  181.     int cur = u;
  182.     int pre = -1;
  183.     do
  184.     {
  185.         if(pre == -1)
  186.         {
  187.             ans += stateOn[cur] * dist(u , cur) + SumW[cur];
  188.         }
  189.         else
  190.         {
  191.             ans += (stateOn[cur] - stateOn[pre]) * dist(u , cur) + SumW[cur] - sumChild[cur][pos[pre]];
  192.         }
  193.         pre = cur;
  194.         cur = par[cur];
  195.     }
  196.     while(cur != 0);
  197.  
  198.     cur = u;
  199.     pre = -1;
  200.  
  201.     do
  202.     {
  203.         //if(u == 2) cout << cur << endl;
  204.         SumW[cur] += dist(u , cur);
  205.         stateOn[cur]++;
  206.         if(pre != -1)
  207.         {
  208.             sumChild[cur][pos[pre]] += dist(u , cur);
  209.         }
  210.         pre = cur;
  211.         cur = par[cur];
  212.     }
  213.     while(cur != 0);
  214.  
  215.     //cout << u << " " << ans << endl;
  216.  
  217. }
  218.  
  219. void Del(int u)
  220. {
  221.     int cur = u;
  222.     int pre = -1;
  223.  
  224.     do
  225.     {
  226.         SumW[cur] -= dist(u , cur);
  227.         stateOn[cur]--;
  228.         if(pre != -1)
  229.         {
  230.             sumChild[cur][pos[pre]] -= dist(u , cur);
  231.         }
  232.         pre = cur;
  233.         cur = par[cur];
  234.     }
  235.     while(cur != 0);
  236.  
  237.     cur = u;
  238.     pre = -1;
  239.  
  240.     do
  241.     {
  242.         if(pre == -1)
  243.         {
  244.             ans -= stateOn[cur] * dist(u , cur) + SumW[cur];
  245.         }
  246.         else
  247.         {
  248.             ans -= ((stateOn[cur] - stateOn[pre]) * dist(u , cur) + SumW[cur] - sumChild[cur][pos[pre]]);
  249.         }
  250.         pre = cur;
  251.         cur = par[cur];
  252.     }
  253.     while(cur != 0);
  254. }
  255. void solve(void)
  256. {
  257.     int subtask; cin >> subtask;
  258.     cin >> n >> q;
  259.     for(int i = 1; i < n; i++)
  260.     {
  261.         int u , v , c;
  262.         cin >> u >> v >> c;
  263.         a[u].push_back(ii(v , c));
  264.         a[v].push_back(ii(u , c));
  265.     }
  266.     for(int i = 1; i <= n; i++)
  267.     {
  268.         char c ; cin >> c;
  269.         if(c == '1') state[i] = 1;
  270.     }
  271.  
  272.     dfs(1 , -1);
  273.     BuildLca();
  274.     cd(1 , 0);
  275.  
  276.     for(int i = 1; i <= n; i++)
  277.     {
  278.         sumChild[i] = vector <ll> (numchild[i] + 1 , 0);
  279.     }
  280.  
  281.     for(int i = 1; i <= n; i++)
  282.     {
  283.         if(state[i]) Add(i);
  284.     }
  285.     cout << ans << " ";
  286.     while(q--)
  287.     {
  288.         int u; cin >> u;
  289.         state[u] ^= 1;
  290.         if(state[u]) Add(u);
  291.         else Del(u);
  292.         cout << ans << " ";
  293.     }
  294. }
  295. /**
  296. 1
  297. 6 0
  298. 1 2 2
  299. 1 3 1
  300. 3 4 2
  301. 3 5 3
  302. 3 6 1
  303. 011010
  304.  
  305.  
  306. **/
  307. signed main()
  308. {
  309.    ios_base::sync_with_stdio(0);
  310.    cin.tie(0);
  311.    cout.tie(0);
  312.  
  313.    #define task "bubblempire"
  314.  
  315.    if(fopen(task".inp","r"))
  316.    {
  317.        freopen(task".inp","r",stdin);
  318.        freopen(task".out","w",stdout);
  319.    }
  320.  
  321.    int tc = 1;
  322. //   cin >> tc;
  323.    while(tc--) solve();
  324.  
  325. //   execute;
  326. }
  327.  
  328.  
  329.  
  330.  
Success #stdin #stdout 0.02s 116104KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/WwPySl
language:
C++14 (clang 8.0)
created:
5 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!