Submission #1093581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093581		fryingduc	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	5053 ms	476408 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<long long> tree;
  vector<long long> lazy;
  segment_tree() {}
  segment_tree(int n) : n(n), tree(n * 4 + 6), lazy(n * 4 + 6) {}
  void down(int ind, int l, int r) {
    tree[ind] += 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]);    
  }
  inline long long get(int ind, int l, int r, int x, int y) {
    if(lazy[ind]) down(ind, l, r);
    if(l > y || r < x) return 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);
  }
  inline long long get(int x, int y) {
    return get(1, 1, n, x, y);
  }
};
pair<long long, long long> operator+(const pair<long long, long long> &x, const pair<long long, long long> &y) {
  pair<long long, long long> res = x;
  if(y.first > x.first) {
    res.first = y.first;
    res.second = max(x.first, y.second); 
  }
  else if(y.first > x.second) {
    res.second = y.first;
  }
  return res;
}
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<vector<int>> up;
  vector<int> h;
  vector<int> tin, tout;
  vector<int> vertices;
  vector<int> rev;
  segment_tree st;
  multiset<long long> stx;
  int LG;
  int timer;
  tree() {}
  tree(int root) : root(root) {
    vertices.push_back(root);
  }
  void pre_dfs(int u, int prev, long long dep) {
    tin[u] = ++timer;
    st.update(tin[u], tin[u], dep);
    for(auto e:adj[u]) {
      int v = e.first;
      if(v == prev) continue;
      h[v] = h[u] + 1;
      up[v][0] = u;
      for(int i = 1; i <= LG; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
      }
      pre_dfs(v, u, dep + e.second);
    }
    tout[u] = timer;
  }
  int kth_anc(int u, int k) {
    for(int i = LG; i >= 0; --i) {
      if(k >> i & 1) u = up[u][i];
    }
    return u;
  }
  void resize(int n) {
    adj.resize(n + 1);
    tin.resize(n + 1);
    tout.resize(n + 1);
    h.resize(n + 1);
    rev.resize(n + 1, -1);
    st = segment_tree(n);
    up.resize(n + 1, vector<int>(LG + 1));
    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;
    LG = lg2[n + 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);
    for(int i = 0; i < (int)adj[root].size(); ++i) {
      int v = adj[root][i].first;
      rev[v] = i;
      stx.insert(st.get(tin[v], tout[v]));
    }
  }
  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(up[u][0] == v) swap(u, v);
    int ancestor = kth_anc(v, h[v] - 1);
    long long temp = st.get(tin[ancestor], tout[ancestor]);
    stx.erase(stx.find(temp));
    st.update(tin[v], tout[v], w);
    temp = st.get(tin[ancestor], tout[ancestor]);
    stx.insert(temp);
  }
  long long get() {
    if(stx.empty()) return 0;
    if((int)stx.size() < 2) {
      return *stx.rbegin();
    }
    return *stx.rbegin() + *(--(--stx.end()));
  }
} trees[maxn];
//void update_forest(int edge_id, long long new_weight) {
//  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]) {
//    long long last_res = trees[cur_tree].get();
//    if(res_per_tree.find(last_res) != res_per_tree.end()) {
//      res_per_tree.erase(res_per_tree.find(last_res));
//    }
//    trees[cur_tree].update(u, v, new_weight - last_weight);
//    res_per_tree.insert(trees[cur_tree].get());
//  }
//  weights[edge_id] = new_weight;
//}
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].get());
  }
  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]) {
      long long last_res = trees[cur_tree].get();
//      if(res_per_tree.find(last_res) != res_per_tree.end()) {
        res_per_tree.erase(res_per_tree.find(last_res));
//      }
      trees[cur_tree].update(u, v, new_weight - last_weight);
      res_per_tree.insert(trees[cur_tree].get());
    }
    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();
  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: 0 / 24
• Subtask 6: 0 / 27