This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//
// Created by adavy on 7/14/2024.
//
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
int INF = 1e18;
vector<vector<pair<int,int>>> adj; // (next, id))
vector<vector<int>> my_trees; // edges
vector<int> w;
vector<bool> vis; // for centroid decomposition
multiset<int,greater<int>> anses;
struct segtree{
int sz = 1;
vector<int> seg,lz;
void init(int n){
while (sz < n) sz *= 2;
seg.resize(2*sz,0);
lz.resize(2*sz,0);
}
// range adds and maximums
void pushdown(int rt, int tl, int tr){
seg[rt] += lz[rt];
if (tl != tr){
lz[2*rt] += lz[rt];
lz[2*rt+1] += lz[rt];
}
lz[rt] = 0;
}
void add(int x, int l, int r, int rt, int tl, int tr){
pushdown(rt,tl,tr);
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
lz[rt] += x;
pushdown(rt,tl,tr);
return;
}
int tm = (tl+tr)/2;
add(x,l,r,2*rt,tl,tm);
add(x,l,r,2*rt+1,tm+1,tr);
seg[rt] = max(seg[2*rt],seg[2*rt+1]);
}
int query(int l, int r, int rt, int tl, int tr){
pushdown(rt,tl,tr);
if (l > tr || r < tl) return -INF;
if (l <= tl && tr <= r) return seg[rt];
int tm = (tl+tr)/2;
return max(query(l,r,2*rt,tl,tm),query(l,r,2*rt+1,tm+1,tr));
}
};
struct tree{
map<int,int> edge_to_node; // edge,node
vector<int> node_to_group;
vector<int> group_rep,group_wt,group_set;
int T=0,G=0;
int name = 0;
vector<int> ton,toff; // ton = the node number
segtree st;
multiset<int,greater<int>> group_vals;
set<int> is_leader;
int my_max = 0;
void dfs(int u, int p){
//if (vis[u]) assert(false);
int cur_name = T;
node_to_group.push_back(-1);
ton.push_back(T++); toff.push_back(-1);
for (auto&[v,i]:adj[u]) if (v != p && !vis[v]){
my_trees[i].push_back(name);
int my_name = T;
if (u == name){
group_rep.push_back(T);
group_wt.push_back(w[i]);
is_leader.insert(T);
}
node_to_group[T] = G;
edge_to_node[i] = my_name;
dfs(v,u);
if (u == name){
G++;
}
}
toff[cur_name] = T;
}
void update_edge(int e, int w_change){
anses.erase(anses.find(my_max));
int nd = edge_to_node[e];
int gp = node_to_group[nd];
group_vals.erase(group_vals.find(group_set[gp]));
if (is_leader.count(nd)){
group_wt[gp] += w_change;
}
else {
st.add(w_change,ton[nd],toff[nd]-1,1,0,st.sz-1);
}
int new_max = group_wt[gp] + st.query(ton[group_rep[gp]],toff[group_rep[gp]]-1,1,0,st.sz-1);
group_vals.insert(new_max);
group_set[gp] = new_max;
// now, get the maximum two elements from the multiset
my_max = gmx();
anses.insert(my_max);
}
int gmx(){
int mx1=0,mx2=0;
if (G==1){
mx1 = *group_vals.begin();
}
else if (G >= 2){
mx1 = *group_vals.begin();
mx2 = *next(group_vals.begin());
}
return mx1 + mx2;
}
void init(int rt){
name = rt;
dfs(rt,-1);
st.init(T+1); // check!!!
for (auto& [e,n]:edge_to_node){
if (!is_leader.count(n)){
st.add(w[e],ton[n],toff[n]-1,1,0,st.sz-1);
}
}
for(int g=0;g<G;++g){
group_set.push_back(group_wt[g] + st.query(ton[group_rep[g]],toff[group_rep[g]]-1,1,0,st.sz-1));
group_vals.insert(group_set[g]);
}
// output edge to node
my_max = gmx();
anses.insert(my_max);
}
};
vector<tree> trees;
vector<int> n_sz;
void init_sz(int u, int p){
n_sz[u] = 1;
for(auto&[v,i]:adj[u]) if (v != p && !vis[v]){
init_sz(v,u);
n_sz[u] += n_sz[v];
}
}
int find_centroid(int u, int p, int n){
for(auto&[v,i]:adj[u]) if (v != p && !vis[v]){
if (n_sz[v] > n/2) return find_centroid(v,u,n);
}
return u;
}
void centroid_decomp(int u){
init_sz(u,-1);
int c = find_centroid(u,-1,n_sz[u]);
//cout << "centroid is " << c << endl;
trees[c].init(c);
vis[c] = 1;
for(auto&[v,i]:adj[c]) if (!vis[v]){
centroid_decomp(v);
}
}
// let's do a CENTROID DECOMPOSITION
signed main(){
std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n,q,mw; cin >> n >> q >> mw;
adj.resize(n);
vis.resize(n,0);
n_sz.resize(n,0);
w.resize(n-1);
for(int i=0;i<n-1;++i){
int a,b,c; cin >> a >> b >> c; a--; b--;
adj[a].push_back({b,i});
adj[b].push_back({a,i});
w[i] = c;
}
my_trees.resize(n-1);
trees.resize(n,tree());
centroid_decomp(0);
// for each edge, output its' trees
/*
for (int i=0;i<n-1;++i){
cout << "edge " << i ;
for(auto&x:my_trees[i]){
cout << " tree " << x << " ";
}
cout << endl;
}*/
int last = 0;
for(int i=0;i<q;++i){
int d,e; cin >> d >> e;
int dprime = (d+last)%(n-1);
int eprime = (e+last)%mw;
int wchange = eprime - w[dprime];
w[dprime] = eprime;
for(auto&ct:my_trees[dprime]){
trees[ct].update_edge(dprime,wchange);
}
last = *anses.begin();
cout << last << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |