#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};
void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;
template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "["; REP(i, U) out << v[i] << ", "; out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "["; REP(i, v.size()) out << v[i] << ", "; out << "]"; return out;}
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
struct node{
ll ans = 0, lazy = 0;
void apply(int l, int r, ll val){
ans += val;
lazy += val;
}
};
struct segtree{
node comb(node const &a, node const &b){
node res;
res.ans = max(a.ans, b.ans);
return res;
}
void push(int l, int r, int v){
tree[v<<1].lazy += tree[v].lazy;
tree[v<<1|1].lazy += tree[v].lazy;
tree[v<<1].ans += tree[v].lazy;
tree[v<<1|1].ans += tree[v].lazy;
tree[v].lazy = 0;
}
int sz;
vector<node> tree;
segtree(){}
segtree(int _sz){ // tree is resized to default values set in node
sz = 1; while(sz < _sz) sz<<=1;
tree.resize(2*sz);
}
void build(vector<node> &init){
for(int i = 0; i < sz; ++i)
if(i < init.size())
tree[i+sz] = init[i];
for(int i = sz-1; i > 0; --i)
tree[i] = comb(tree[i<<1], tree[i<<1|1]);
}
node query(int l, int r){return query0(l, r, 0, sz, 1);}
node query0(int l, int r, int beg, int end, int v){
if(beg >= l && end <= r)
return tree[v];
push(beg, end, v);
int mid = (beg + end) >> 1;
node res;
if(beg >= r || mid <= l) res = query0(l, r, mid, end, v<<1|1); //[beg, mid]
else if(mid >= r || end <= l) res = query0(l, r, beg, mid, v<<1);
else res = comb(query0(l, r, beg, mid, v<<1), query0(l, r, mid, end, v<<1|1));
return res;
}
template<typename... T>
void upd(int l, int r, T ...args){upd0(l, r, 0, sz, 1, args...);}
template<typename... T>
void upd0(int l, int r, int beg, int end, int v, T ...args){
if(beg >= r || end <= l)
return;
if(beg >= l && end <= r){
tree[v].apply(beg, end, args...);
return;
}
push(beg, end, v);
int mid = (beg + end) >> 1;
upd0(l, r, beg, mid, v<<1, args...);
upd0(l, r, mid, end, v<<1|1, args...);
tree[v] = comb(tree[v<<1], tree[v<<1|1]);
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, q; ll w;
cin >> n >> q; cin >> w;
vector<vector<array<ll, 2>>> g(n);
vector<array<ll, 3>> edges(n - 1);
// centroids for full, but too hard to impl, impl at the end if time
REP(i, n - 1){
ll a, b, c;
cin >> a >> b >> c;
a--; b--;
g[a].pb({b, i});
g[b].pb({a, i});
edges[i] = {a, b, c};
}
auto solve12 = [&](){
int diam1, diam2;
vector<ll> dist(n, 0);
function<void(int, int)> dfs = [&](int v, int p){
for(auto x : g[v]){
if(x[0] == p) continue;
ll weight = edges[x[1]][2];
dist[x[0]] = dist[v] + weight;
dfs(x[0], v);
}
};
dfs(0, -1); diam1 = max_element(all(dist)) - dist.begin();
dist[diam1] = 0; dfs(diam1, -1); diam2 = max_element(all(dist)) - dist.begin();
ll last = 0;
REP(i, q){
ll d, e;
cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % w;
edges[d][2] = e;
dist[diam1] = 0;
dfs(diam1, -1); int nxt_diam2 = max_element(all(dist)) - dist.begin();
ll nxt_diamw2 = *max_element(all(dist));
dist[diam2] = 0; dfs(diam2, -1); int nxt_diam1 = max_element(all(dist)) - dist.begin();
ll nxt_diamw1 = *max_element(all(dist));
if(nxt_diamw1 > nxt_diamw2){
last = nxt_diamw1;
diam1 = nxt_diam1;
}
else{
last = nxt_diamw2;
diam2 = nxt_diam2;
}
cout << last << "\n";
}
};
//solve12();
auto solve = [&](){
vector<multiset<ll>> depths(n); // for each centroid
multiset<ll> answers;
vector<int> par(n, -1); // parent in centroid tree
vector<int> lev(n, 0); // level of centroid
const int mxlv = 19;
vector<vector<int>> in(mxlv, vector<int>(n, -1));
vector<vector<int>> out(mxlv, vector<int>(n, -1));
vector<vector<int>> sub_root(mxlv, vector<int>(n, -1));
vector<segtree> segtrees(mxlv, segtree(n));
vector<int> ptr(mxlv, 0); //vector<vector<node>> init(mxlv, vector<node>(n));
vector<bool> dead(n, false);
vector<int> sub(n, 0);
auto compute_ans = [](multiset<ll> &se){
multiset<ll> :: reverse_iterator it = se.rbegin();
if(se.size() == 0) return 0ll;
ll res = *it;
if(se.size() > 1){
it++; res += *it;
}
return res;
};
function<void(int, int)> getsub = [&](int v, int p){
sub[v] = 1;
for(auto x : g[v]){
if(x[0] == p) continue;
if(dead[x[0]]) continue;
getsub(x[0], v);
sub[v] += sub[x[0]];
}
};
function<int(int, int, int)> get_centroid = [&](int v, int p, int total_size){
int heavy_child = -1;
for(auto x : g[v]){
if(x[0] == p || dead[x[0]]) continue;
if(sub[x[0]] > total_size / 2)
heavy_child = x[0];
}
if(heavy_child == -1)
return v;
else
return get_centroid(heavy_child, v, total_size);
};
function<void(int, int)> decompose = [&](int v, int p){
// find centroid of this subtree
getsub(v, -1);
int centroid = get_centroid(v, -1, sub[v]);
par[centroid] = p; // par in centroid tree
if(p != -1) lev[centroid] = lev[p] + 1;
int level = lev[centroid];
int t = ptr[level];
function<void(int, int, ll, int)> dfs = [&](int v, int p, ll depth, int subrootnum){
in[level][v] = t;
segtrees[level].upd(t, t + 1, depth);
sub_root[level][v] = subrootnum;
t++;
for(auto x : g[v]){
if(x[0] == p || dead[x[0]]) continue;
ll weight = edges[x[1]][2];
dfs(x[0], v, depth + weight, subrootnum);
}
out[level][v] = t;
};
for(auto x : g[centroid]){
if(dead[x[0]]) continue;
ll weight = edges[x[1]][2];
dfs(x[0], centroid, weight, x[0]);
ptr[level] = t;
}
for(auto x : g[centroid]){
if(dead[x[0]]) continue;
depths[centroid].insert(segtrees[level].query(in[level][x[0]], out[level][x[0]]).ans);
}
answers.insert(compute_ans(depths[centroid]));
dead[centroid] = true;
for(auto x : g[centroid]){
if(dead[x[0]]) continue;
decompose(x[0], centroid);
}
};
decompose(0, -1);
ll last = 0;
REP(i, q){
ll d, e;
cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % w;
auto edge = edges[d];
int frs; // prvy centroid ktoreho sa to dotkne
if(lev[edge[0]] < lev[edge[1]])
frs = edge[0];
else
frs = edge[1];
while(frs != -1){
answers.erase(answers.find(compute_ans(depths[frs])));
int centroid_lev = lev[frs];
int desc;
if(in[centroid_lev][edge[0]] > in[centroid_lev][edge[1]])
desc = edge[0];
else
desc = edge[1];
ll delta = e - edge[2];
int root = sub_root[centroid_lev][desc];
depths[frs].erase(depths[frs].find(segtrees[centroid_lev].query(in[centroid_lev][root], out[centroid_lev][root]).ans));
segtrees[centroid_lev].upd(in[centroid_lev][desc], out[centroid_lev][desc], delta);
depths[frs].insert(segtrees[centroid_lev].query(in[centroid_lev][root], out[centroid_lev][root]).ans);
answers.insert(compute_ans(depths[frs]));
frs = par[frs];
}
edges[d][2] = e;
last = *answers.rbegin();
cout << last << "\n";
}
};
solve();
return 0;
}
Compilation message
diameter.cpp: In member function 'void segtree::build(std::vector<node>&)':
diameter.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | if(i < init.size())
| ~~^~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:138:10: warning: variable 'solve12' set but not used [-Wunused-but-set-variable]
138 | auto solve12 = [&](){
| ^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
512 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
512 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
512 KB |
Output is correct |
19 |
Correct |
24 ms |
1560 KB |
Output is correct |
20 |
Correct |
28 ms |
1568 KB |
Output is correct |
21 |
Correct |
33 ms |
1516 KB |
Output is correct |
22 |
Correct |
42 ms |
1644 KB |
Output is correct |
23 |
Correct |
59 ms |
7912 KB |
Output is correct |
24 |
Correct |
91 ms |
7784 KB |
Output is correct |
25 |
Correct |
84 ms |
7912 KB |
Output is correct |
26 |
Correct |
93 ms |
8296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
2 ms |
364 KB |
Output is correct |
4 |
Correct |
14 ms |
620 KB |
Output is correct |
5 |
Correct |
69 ms |
1540 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
2 ms |
876 KB |
Output is correct |
8 |
Correct |
2 ms |
876 KB |
Output is correct |
9 |
Correct |
4 ms |
876 KB |
Output is correct |
10 |
Correct |
20 ms |
1132 KB |
Output is correct |
11 |
Correct |
96 ms |
2284 KB |
Output is correct |
12 |
Correct |
10 ms |
7656 KB |
Output is correct |
13 |
Correct |
11 ms |
7656 KB |
Output is correct |
14 |
Correct |
14 ms |
7784 KB |
Output is correct |
15 |
Correct |
37 ms |
8040 KB |
Output is correct |
16 |
Correct |
142 ms |
9192 KB |
Output is correct |
17 |
Correct |
222 ms |
126548 KB |
Output is correct |
18 |
Correct |
226 ms |
126548 KB |
Output is correct |
19 |
Correct |
231 ms |
126676 KB |
Output is correct |
20 |
Correct |
282 ms |
126932 KB |
Output is correct |
21 |
Correct |
623 ms |
127316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
1644 KB |
Output is correct |
2 |
Correct |
43 ms |
1644 KB |
Output is correct |
3 |
Correct |
202 ms |
2164 KB |
Output is correct |
4 |
Correct |
399 ms |
2796 KB |
Output is correct |
5 |
Correct |
56 ms |
15080 KB |
Output is correct |
6 |
Correct |
146 ms |
15336 KB |
Output is correct |
7 |
Correct |
491 ms |
16104 KB |
Output is correct |
8 |
Correct |
1000 ms |
16620 KB |
Output is correct |
9 |
Correct |
306 ms |
64144 KB |
Output is correct |
10 |
Correct |
464 ms |
64216 KB |
Output is correct |
11 |
Correct |
1221 ms |
64884 KB |
Output is correct |
12 |
Correct |
2058 ms |
65580 KB |
Output is correct |
13 |
Correct |
711 ms |
127580 KB |
Output is correct |
14 |
Correct |
872 ms |
127580 KB |
Output is correct |
15 |
Correct |
1836 ms |
128160 KB |
Output is correct |
16 |
Correct |
2825 ms |
128144 KB |
Output is correct |
17 |
Execution timed out |
5069 ms |
128172 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4145 ms |
129000 KB |
Output is correct |
2 |
Correct |
4284 ms |
128576 KB |
Output is correct |
3 |
Correct |
4188 ms |
128532 KB |
Output is correct |
4 |
Correct |
4293 ms |
128620 KB |
Output is correct |
5 |
Correct |
4051 ms |
128272 KB |
Output is correct |
6 |
Correct |
3748 ms |
128076 KB |
Output is correct |
7 |
Execution timed out |
5048 ms |
132588 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
512 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
512 KB |
Output is correct |
19 |
Correct |
24 ms |
1560 KB |
Output is correct |
20 |
Correct |
28 ms |
1568 KB |
Output is correct |
21 |
Correct |
33 ms |
1516 KB |
Output is correct |
22 |
Correct |
42 ms |
1644 KB |
Output is correct |
23 |
Correct |
59 ms |
7912 KB |
Output is correct |
24 |
Correct |
91 ms |
7784 KB |
Output is correct |
25 |
Correct |
84 ms |
7912 KB |
Output is correct |
26 |
Correct |
93 ms |
8296 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
2 ms |
364 KB |
Output is correct |
30 |
Correct |
14 ms |
620 KB |
Output is correct |
31 |
Correct |
69 ms |
1540 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
2 ms |
876 KB |
Output is correct |
34 |
Correct |
2 ms |
876 KB |
Output is correct |
35 |
Correct |
4 ms |
876 KB |
Output is correct |
36 |
Correct |
20 ms |
1132 KB |
Output is correct |
37 |
Correct |
96 ms |
2284 KB |
Output is correct |
38 |
Correct |
10 ms |
7656 KB |
Output is correct |
39 |
Correct |
11 ms |
7656 KB |
Output is correct |
40 |
Correct |
14 ms |
7784 KB |
Output is correct |
41 |
Correct |
37 ms |
8040 KB |
Output is correct |
42 |
Correct |
142 ms |
9192 KB |
Output is correct |
43 |
Correct |
222 ms |
126548 KB |
Output is correct |
44 |
Correct |
226 ms |
126548 KB |
Output is correct |
45 |
Correct |
231 ms |
126676 KB |
Output is correct |
46 |
Correct |
282 ms |
126932 KB |
Output is correct |
47 |
Correct |
623 ms |
127316 KB |
Output is correct |
48 |
Correct |
8 ms |
1644 KB |
Output is correct |
49 |
Correct |
43 ms |
1644 KB |
Output is correct |
50 |
Correct |
202 ms |
2164 KB |
Output is correct |
51 |
Correct |
399 ms |
2796 KB |
Output is correct |
52 |
Correct |
56 ms |
15080 KB |
Output is correct |
53 |
Correct |
146 ms |
15336 KB |
Output is correct |
54 |
Correct |
491 ms |
16104 KB |
Output is correct |
55 |
Correct |
1000 ms |
16620 KB |
Output is correct |
56 |
Correct |
306 ms |
64144 KB |
Output is correct |
57 |
Correct |
464 ms |
64216 KB |
Output is correct |
58 |
Correct |
1221 ms |
64884 KB |
Output is correct |
59 |
Correct |
2058 ms |
65580 KB |
Output is correct |
60 |
Correct |
711 ms |
127580 KB |
Output is correct |
61 |
Correct |
872 ms |
127580 KB |
Output is correct |
62 |
Correct |
1836 ms |
128160 KB |
Output is correct |
63 |
Correct |
2825 ms |
128144 KB |
Output is correct |
64 |
Execution timed out |
5069 ms |
128172 KB |
Time limit exceeded |