fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long 
  4. #define el cout << '\n'
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn  = 3e5;
  12. const int maxlog = 18;
  13.  
  14. int subtask, n, q, dist[maxn + 10], sz[maxn + 10], p[maxn + 10][maxlog + 5], tin[maxn + 10], tout[maxn + 10], timer = 0;
  15. int par_centroid[maxn + 10];
  16. ll cnt[maxn + 10], sum_dist[maxn + 10], sum_dist_par[maxn + 10];
  17. bool check[maxn + 10], is_centroid[maxn + 10];
  18. ll ans = 0;
  19. vector<ii> adj[maxn + 10];
  20.  
  21. void build_sz(int top, int par)
  22. {
  23.     sz[top] = 1;
  24.     for (ii pr : adj[top])
  25.     {
  26.         int next_top = pr.fi;
  27.         if (next_top == par || is_centroid[next_top])
  28.             continue;
  29.         build_sz(next_top, top);
  30.         sz[top] += sz[next_top];
  31.     }
  32. }
  33. int find_centroid(int top, int par, int tree_sz)
  34. {
  35.     for (ii pr : adj[top])
  36.     {
  37.         int next_top = pr.fi;
  38.         if (next_top == par || is_centroid[next_top])
  39.             continue;
  40.         if (2 * sz[next_top] > tree_sz)
  41.             return find_centroid(next_top, top, tree_sz);
  42.     }
  43.     return top;
  44. }
  45. void build_centroid_tree(int top, int par = -1)
  46. {
  47.     build_sz(top, -1);
  48.     int centroid = find_centroid(top, -1, sz[top]);
  49.     is_centroid[centroid] = 1;
  50.  
  51.     if (par != -1)
  52.     {
  53.         // cout << par << ' ' << centroid, el;
  54.         par_centroid[centroid] = par;
  55.     }
  56.  
  57.     for (ii pr : adj[centroid])
  58.     {
  59.         int next_top = pr.fi;
  60.         if (!is_centroid[next_top])
  61.             build_centroid_tree(next_top, centroid);
  62.     }
  63. }
  64. void dfs(int top, int par = 0)
  65. {
  66.     tin[top] = ++timer;
  67.     p[top][0] = par;
  68.     for (int i = 1; i <= maxlog; i++)
  69.         p[top][i] = p[p[top][i - 1]][i - 1];
  70.     for (ii pr : adj[top])
  71.     {
  72.         int next_top = pr.fi;
  73.         int w = pr.se;
  74.         if (next_top == par)
  75.             continue;
  76.         dist[next_top] = dist[top] + w;
  77.         dfs(next_top, top);
  78.     }
  79.     tout[top] = timer;
  80. }
  81. bool is_ancestor(int x, int y)
  82. {
  83.     if (x == 0 || y == 0)
  84.         return 1;
  85.     return tin[x] <= tin[y] && tout[y] <= tout[x];
  86. }
  87. int get_lca(int x, int y)
  88. {
  89.     if (is_ancestor(x, y))
  90.         return x;
  91.     if (is_ancestor(y, x))
  92.         return y;
  93.     for (int i = maxlog; i >= 0; i--)
  94.         if (!is_ancestor(p[x][i], y))
  95.             x = p[x][i];
  96.     return p[x][0];
  97. }
  98. int get_dist(int x, int y)
  99. {
  100.     return dist[x] + dist[y] - 2 * dist[get_lca(x, y)];
  101. }
  102. void update(int x, int mobius)
  103. {
  104.     int pre_par = 0;
  105.     for (int u = x; u; u = par_centroid[u])
  106.     {
  107.         cnt[u] += mobius;
  108.         sum_dist[u] += mobius * get_dist(u, x);
  109.         if (pre_par)
  110.             sum_dist_par[pre_par] += mobius * get_dist(u, x);
  111.         pre_par = u;
  112.         // cout << u << ' ' << x << ' ' << cnt[u] << ' ' << sum_dist[u], el;
  113.     }
  114. }
  115. ll get(int x, int mobius)
  116. {
  117.     ll ans = 0;
  118.     int pre_par = 0;
  119.     for (int u = x; u; u = par_centroid[u])
  120.     {
  121.         // cout << pre_par << ' ' << cnt[u] << ' ' << cnt[pre_par] << ' ' << sum_dist[u] << ' ' << sum_dist_par[pre_par], el;
  122.         ans += mobius * (1ll * get_dist(u, x) * (cnt[u] - cnt[pre_par]) + sum_dist[u] - sum_dist_par[pre_par]);
  123.         pre_par = u;
  124.     }
  125.     return ans;
  126. }
  127.  
  128. int main()
  129. {
  130.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  131.     if (fopen("BUBBLEMPIRE.INP", "r"))
  132.     {
  133.         freopen("BUBBLEMPIRE.INP", "r", stdin);
  134.         freopen("BUBBLEMPIRE.OUT", "w", stdout);
  135.     }
  136.  
  137.     cin >> subtask;
  138.     cin >> n >> q;
  139.     for (int i = 1; i < n; i++)
  140.     {
  141.         int x, y;
  142.         ll w;
  143.         cin >> x >> y >> w;
  144.         adj[x].push_back(ii(y, w));
  145.         adj[y].push_back(ii(x, w));
  146.     }
  147.     dfs(1);
  148.     build_centroid_tree(1);
  149.     for (int i = 1; i <= n; i++)
  150.     {
  151.         char c;
  152.         cin >> c;
  153.         check[i] = c - '0';
  154.         if (check[i] == 1)
  155.         {
  156.             ans += get(i, 1);
  157.             update(i, 1);
  158.         }
  159.     }
  160.     cout << ans << ' ';
  161.     while (q--)
  162.     {
  163.         int x;
  164.         cin >> x;
  165.         if (check[x] == 0)
  166.         {
  167.             ans += get(x, 1);
  168.             update(x, 1);
  169.         }
  170.         else
  171.         {
  172.             update(x, -1);
  173.             ans += get(x, -1);
  174.         }
  175.         check[x] ^= 1;
  176.         cout << ans << ' ';
  177.     }
  178. }
Success #stdin #stdout 0.01s 15112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ciKsVf
language:
C++14 (gcc 8.3)
created:
1 day 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!