Submission #1093644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093644		fryingduc	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3424 ms	443116 KiB

diameter

#include "bits/stdc++.h"
using namespace std;
 
const int maxn = 1e5 + 5;
int n, q;
int edge_u[maxn], edge_v[maxn];
long long weights[maxn];
int roots[maxn];
vector<pair<int, int>> g[maxn];
bool del[maxn];
int sz[maxn];
vector<int> forest[maxn];
vector<int> contained_in_forest[maxn];
int num_trees;
int lg2[maxn];
 
multiset<long long> res_per_tree;
 
long long res;
 
long long encode_w;
 
struct segment_tree {
  int n;
  vector<pair<long long, int>> tree;
  vector<long long> lazy;
  vector<pair<long long, int>> a;
  segment_tree() {}
  segment_tree(int n) : n(n), tree(n * 4 + 6), lazy(n * 4 + 6) {}
  void build(int ind, int l, int r) {
    if(l == r) {
      tree[ind] = a[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(ind << 1, l, mid);
    build(ind << 1 | 1, mid + 1, r);
    tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]); 
  }
  void down(int ind, int l, int r) {
    tree[ind].first += lazy[ind];
    if(l != r) {
      lazy[ind << 1] += lazy[ind];
      lazy[ind << 1 | 1] += lazy[ind];
    }
    lazy[ind] = 0;
  }
  void update(int ind, int l, int r, int x, int y, long long val) {
    if(lazy[ind]) down(ind, l, r);
    if(l > y || r < x) return;
    if(x <= l and r <= y) {
      lazy[ind] += val;
      down(ind, l, r);
      return;
    }
    int mid = (l + r) >> 1;
    update(ind << 1, l, mid, x, y, val);
    update(ind << 1 | 1, mid + 1, r, x, y, val);
    tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]);    
  }
  pair<long long, int> get(int ind, int l, int r, int x, int y) {
    if(lazy[ind]) down(ind, l, r);
    if(l > y || r < x) return make_pair(0, 0);
    if(x <= l and r <= y) {
      return tree[ind];
    }
    int mid = (l + r) >> 1;
    return max(get(ind << 1, l, mid, x, y), get(ind << 1 | 1, mid + 1, r, x, y));
  }
  inline void update(int x, int y, long long val) {
    update(1, 1, n, x, y, val);
  }
  pair<long long, int> get(int x, int y) {
    if(x > y) return make_pair(0, 0);
    return get(1, 1, n, x, y);
  }
  void build(vector<pair<long long, int>> &va) {
    a = va;
    build(1, 1, n);
  }
  pair<long long, int> get() {
    return get(1, n);
  }
};
int find_centroid(int u, int prev, int n) {
  for(const auto &e:g[u]) {
    if(e.first != prev and !del[e.first] and sz[e.first] * 2 > n) 
      return find_centroid(e.first, u, n);
  }
  return u;
}
void re_dfs(int u, int prev) {
  sz[u] = 1;
  for(const auto &e:g[u]) {
    if(e.first == prev || del[e.first]) continue;
    re_dfs(e.first, u);
    sz[u] += sz[e.first];
  }
}
void collect_tree(int u, int prev) {
  for(auto e:g[u]) {
    int v = e.first;
    if(v == prev || del[v]) continue;
    forest[num_trees].push_back(e.second);
    contained_in_forest[e.second].push_back(num_trees);
    collect_tree(v, u);
  }
}
void decompose(int u, int prev) {
  re_dfs(u, prev);
  int c = find_centroid(u, prev, sz[u]);
  
  ++num_trees;
  roots[num_trees] = c;
  
  for(auto e:g[c]) {
    int v = e.first;
    if(del[v]) continue;
    forest[num_trees].push_back(e.second);
    contained_in_forest[e.second].push_back(num_trees);
    collect_tree(v, c);
  }
  del[c] = 1;
  for(auto e:g[c]) {
    int v = e.first;
    if(v == prev || del[v]) continue;
    decompose(v, c);
  }
}
struct tree {
  int n;
  int root;
  vector<vector<pair<int, long long>>> adj;
  vector<int> tin, tout;
  vector<int> vertices;
  vector<int> rev;
  vector<pair<long long, int>> max_path;
  long long diameter;
  segment_tree st;
  int LG;
  int timer;
  tree() {}
  tree(int root) : root(root) {
    vertices.push_back(root);
  }
  void pre_dfs(int u, int prev, long long dep, int par) {
    tin[u] = ++timer;
    max_path[tin[u]] = {dep, par};
    for(auto e:adj[u]) {
      int v = e.first;
      if(v == prev) continue;
      pre_dfs(v, u, dep + e.second, (u == root ? v : par));
    }
    tout[u] = timer;
  }
  void resize(int n) {
    adj.resize(n + 1);
    tin.resize(n + 1);
    tout.resize(n + 1);
    rev.resize(n + 1, -1);
    max_path.resize(n + 1);
    st = segment_tree(n);
    timer = 0;
  }
  void build(vector<int> &vec) {
    for(auto i:vec) {
      vertices.push_back(edge_u[i]);
      vertices.push_back(edge_v[i]);
    }
    sort(vertices.begin(), vertices.end());
    vertices.erase(unique(vertices.begin(), vertices.end()), vertices.end());
    
    n = vertices.size();
    root = lower_bound(vertices.begin(), vertices.end(), root) - vertices.begin() + 1;
    resize(n);
    for(auto i:vec) {
      int u = edge_u[i], v = edge_v[i];
      u = lower_bound(vertices.begin(), vertices.end(), u) - vertices.begin() + 1;
      v = lower_bound(vertices.begin(), vertices.end(), v) - vertices.begin() + 1;
      adj[u].emplace_back(v, weights[i]);
      adj[v].emplace_back(u, weights[i]);
    } 
    pre_dfs(root, 0, 0, 0);
    st.build(max_path);
    for(int i = 0; i < (int)adj[root].size(); ++i) {
      int v = adj[root][i].first;
      rev[v] = i;
    }
    refine();
  }
  void update(int u, int v, long long w) {
    u = lower_bound(vertices.begin(), vertices.end(), u) - vertices.begin() + 1;
    v = lower_bound(vertices.begin(), vertices.end(), v) - vertices.begin() + 1;
    
    if(tin[u] > tin[v]) swap(u, v);
    st.update(tin[v], tout[v], w);
    
    refine();
  }
  void refine() {
    pair<long long, int> ft_ver = st.get();
    
    int u = ft_ver.second;
    
    diameter = ft_ver.first;
    diameter += max(st.get(1, tin[u] - 1).first, st.get(tout[u] + 1, n).first);
  }
} trees[maxn];
void solve() {
  cin >> n >> q >> encode_w;
  for(int i = 1; i < n; ++i) {
    int u, v;
    long long w; cin >> u >> v >> w;
    weights[i] = w;
    edge_u[i] = u, edge_v[i] = v;
    g[u].emplace_back(v, i);
    g[v].emplace_back(u, i);
  }
   
  decompose(1, 0);
  for(int i = 1; i <= num_trees; ++i) {
    trees[i] = tree(roots[i]);
    trees[i].build(forest[i]);
    
    res_per_tree.insert(trees[i].diameter);
  }
  while(q--) {
    int edge_id;
    long long new_weight;
    cin >> edge_id >> new_weight;
    edge_id = (1ll * edge_id + 1ll * res) % (n - 1) + 1;
    new_weight = (new_weight + res) % encode_w;
    
    int u = edge_u[edge_id], v = edge_v[edge_id];
    long long last_weight = weights[edge_id];
    for(auto &cur_tree: contained_in_forest[edge_id]) {
      res_per_tree.erase(res_per_tree.find(trees[cur_tree].diameter));
      trees[cur_tree].update(u, v, new_weight - last_weight);
      res_per_tree.insert(trees[cur_tree].diameter);
    }
    weights[edge_id] = new_weight;
    
    res = *res_per_tree.rbegin();
    cout << res << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  lg2[1] = 0;
  for(int i = 2; i < maxn; ++i) {
    lg2[i] = lg2[i / 2] + 1;
  }
 
  solve();
  cerr << "\nTime: " << 1000 * clock() / CLOCKS_PER_SEC << endl;
  return 0;
}
/*
10 10 10000
1 9 1241
5 6 1630
10 5 1630
2 6 853
10 1 511
5 3 760
8 3 1076
4 10 1483
7 10 40
8 2051
5 6294
5 4168
7 1861
0 5244
6 5156
3 3001
8 5267
5 3102
8 3623
 
7 3 0
1 2 6
1 3 2
3 4 2
4 5 2
5 6 5
2 7 1
6 3
3 5
2 4
 
7 1 0
1 2 6
1 3 2
3 4 2
4 5 2
5 6 5
2 7 1
6 3
*/

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27