fork download
copy 
  1. // Author: 4uckd3v - Nguyen Cao Duc
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int MAX_N = 2e5;
  8. const int MAX_Q = 2e5;
  9. const int MOD = 1e9 + 7;
  10.  
  11. struct Query {
  12.     int u, v, w;
  13.     Query() {};
  14.     Query(int u, int v, int w) : u(u), v(v), w(w) {};
  15. };
  16.  
  17. int n, q;
  18. int a[MAX_N + 5];
  19. Query queries[MAX_Q + 5];
  20. vector<int> adj[MAX_N + 5];
  21.  
  22. namespace SUBTASK_1 {
  23.     const int N = 5000;
  24.     const int Q = 5000;
  25.  
  26.     int b[N + 5], par[N + 5], depth[N + 5];
  27.  
  28.     void dfs(int u, int p) {
  29.         par[u] = p;
  30.         depth[u] = depth[p] + 1;
  31.  
  32.         for (int v : adj[u]) {
  33.             if (v == p) continue;
  34.             dfs(v, u);
  35.         };
  36.     };
  37.  
  38.     void updatePath(int u, int v, int w) {
  39.         if (depth[u] > depth[v]) swap(u, v);
  40.         while (depth[v] > depth[u]) {
  41.             b[v] %= w;
  42.             v = par[v];
  43.         };
  44.  
  45.         while (u != v) {
  46.             b[u] %= w, b[v] %= w;
  47.             u = par[u], v = par[v];
  48.         };
  49.  
  50.         b[u] %= w;
  51.     };
  52.  
  53.     void Solve() {
  54.         for (int u = 1; u <= n; u++) {
  55.             b[u] = a[u];
  56.         };
  57.  
  58.         dfs(1, 1);
  59.  
  60.         for (int t = 1; t <= q; t++) {
  61.             int u = queries[t].u, v = queries[t].v, w = queries[t].w;
  62.             updatePath(u, v, w);
  63.  
  64.             ll res = 0;
  65.             for (int u = 1; u <= n; u++) res += b[u] % t;
  66.  
  67.             cout << res << '\n';
  68.         };
  69.     };
  70. };  // namespace SUBTASK_1
  71.  
  72. namespace SUBTASK_2 {
  73.     const int N = MAX_N;
  74.     const int VAL = 2;
  75.  
  76.     int b[N + 5];
  77.     set<int> pos[VAL + 1];
  78.     ll curSum;
  79.  
  80.     bool checkSubtask() {
  81.         for (int u = 1; u <= n; u++) {
  82.             if (a[u] > VAL) return false;
  83.             if (adj[u].size() > 2) return false;
  84.         };
  85.         return true;
  86.     };
  87.  
  88.     void del(int u, int v, int w) {
  89.         while (pos[w].lower_bound(u) != pos[w].end()) {
  90.             auto it = pos[w].lower_bound(u);
  91.             if (*it > v) break;
  92.  
  93.             int node = *it;
  94.             curSum -= a[node];
  95.             // cerr << w << ' ' << node << endl;
  96.             pos[w].erase(it);
  97.         };
  98.     };
  99.  
  100.     void Solve() {
  101.         curSum = 0;
  102.         for (int u = 1; u <= n; u++) {
  103.             b[u] = a[u];
  104.             pos[b[u]].insert(u);
  105.             curSum += b[u];
  106.         };
  107.  
  108.         for (int t = 1; t <= q; t++) {
  109.             int u = queries[t].u, v = queries[t].v, w = queries[t].w;
  110.             if (u > v) swap(u, v);
  111.  
  112.             if (w == 1) {
  113.                 del(u, v, 1);
  114.                 del(u, v, 2);
  115.             } else if (w == 2) {
  116.                 del(u, v, 2);
  117.             };
  118.  
  119.             if (t == 1) {
  120.                 cout << 0 << '\n';
  121.                 continue;
  122.             };
  123.  
  124.             if (t == 2) {
  125.                 cout << pos[1].size() << '\n';
  126.                 continue;
  127.             };
  128.  
  129.             cout << curSum << '\n';
  130.         };
  131.     };
  132. };  // namespace SUBTASK_2
  133.  
  134. int main() {
  135.     ios_base::sync_with_stdio(0);
  136.     cin.tie(0);
  137.     if (fopen("pine.INP", "r")) {
  138.         freopen("pine.INP", "r", stdin);
  139.         freopen("pine.OUT", "w", stdout);
  140.     };
  141.  
  142.     cin >> n >> q;
  143.     for (int u = 1; u <= n; u++) cin >> a[u];
  144.     for (int i = 1; i < n; i++) {
  145.         int u, v;
  146.         cin >> u >> v;
  147.         adj[u].push_back(v);
  148.         adj[v].push_back(u);
  149.     };
  150.  
  151.     for (int t = 1; t <= q; t++) {
  152.         cin >> queries[t].u >> queries[t].v >> queries[t].w;
  153.     };
  154.  
  155.     if (n <= 5000 && q <= 5000)
  156.         return SUBTASK_1::Solve(), 0;
  157.     if (SUBTASK_2::checkSubtask())
  158.         return SUBTASK_2::Solve(), 0;
  159. };
Success #stdin #stdout 0.01s 9756KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OkACrq
language:
C++14 (gcc 8.3)
created:
7 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!