This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define file(name) \
if(fopen(name".inp", "r")) \
freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
const int MAX = 1e5 + 5;
#define int long long
struct Edge {
int u, v;
ll w;
Edge(int u = 0, int v = 0, ll w = 0) : u(u), v(v), w(w) {}
int get(int x) {
return x ^ u ^ v;
}
} e[MAX];
int n, q;
ll W;
vector <int> adj[MAX];
namespace sub12 {
bool check() {
return max(n, q) <= 5000;
}
pair <ll, ll> dp[MAX];
void dfs(int u, int p) {
dp[u] = make_pair(0, 0);
for (int i : adj[u]) if(e[i].get(u) != p) {
int v = e[i].get(u);
dfs(v, u);
if(dp[u].fi < dp[v].fi + e[i].w) {
dp[u].se = dp[u].fi;
dp[u].fi = dp[v].fi + e[i].w;
} else {
dp[u].se = max(dp[u].se, dp[v].fi + e[i].w);
}
}
}
ll get_diameter() {
dfs(1, 0);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans = max(ans, dp[i].fi + dp[i].se);
}
return ans;
}
void solve() {
ll last = 0;
while(q--) {
int d; ll f; cin >> d >> f;
d = (d + last % (n - 1)) % (n - 1) + 1;
f = (f + last) % W;
e[d].w = f;
last = get_diameter();
cout << last << '\n';
}
exit(0);
}
}
namespace sub3 {
bool check() {
return (int) adj[1].size() == n - 1;
}
template < class T, T (*f) (T, T), T (*e) ()>
struct segment_tree {
vector <T> it;
int n;
void set(int u, T p) {
u--;
for (it[u += n] = p; u >>= 1; ) {
it[u] = f(it[u << 1], it[u << 1 | 1]);
}
}
T get(int p) {
return it[p += n - 1];
}
T get(int l, int r) {
l--;
T resl = e(), resr = e();
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1) resl = f(resl, it[l++]);
if(r & 1) resr = f(it[--r], resr);
}
return f(resl, resr);
}
T get_all() {
return it[1];
}
segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
fill(it.begin(), it.end(), T{});
}
};
pair <ll, ll> _max_(pair <ll, ll> a, pair <ll, ll> b) {
pair <ll, ll> res(a.fi, b.fi);
if(res.fi < res.se) swap(res.fi, res.se);
res.se = max(res.se, a.se);
res.se = max(res.se, b.se);
return res;
}
pair <ll, ll> E() { return make_pair(0, 0); }
void solve() {
segment_tree <pair <ll, ll>, _max_, E> it(n);
for (int i : adj[1]) {
it.set(e[i].get(1), make_pair(e[i].w, 0LL));
}
auto get_diameter = [&] () -> ll {
auto res = it.get_all();
return res.fi + res.se;
};
ll last = 0;
while(q--) {
int d; ll f; cin >> d >> f;
d = (d + last % (n - 1)) % (n - 1) + 1;
f = (f + last) % W;
e[d].w = f;
it.set(e[d].get(1), make_pair(f, 0LL));
last = get_diameter();
cout << last << '\n';
}
exit(0);
}
}
namespace sub4 {
template < class T, T (*f) (T, T), T (*e) ()>
struct segment_tree {
vector <T> it;
int n;
void set(int u, T p) {
u--;
for (it[u += n] = p; u >>= 1; ) {
it[u] = f(it[u << 1], it[u << 1 | 1]);
}
}
T get(int p) {
return it[p += n - 1];
}
T get(int l, int r) {
l--;
T resl = e(), resr = e();
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1) resl = f(resl, it[l++]);
if(r & 1) resr = f(it[--r], resr);
}
return f(resl, resr);
}
segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
fill(it.begin(), it.end(), T{});
}
};
ll op(ll a, ll b) { return a > b ? a : b; }
ll E() { return numeric_limits<ll>::min(); }
bool check() {
for (int i = 1; i < n; ++i) {
if(e[i].u > e[i].v) swap(e[i].u, e[i].v);
if(e[i].v / 2 != e[i].u) return false;
}
return true;
}
pair <ll, ll> dp[MAX];
int par[MAX];
void dfs(int u, int p) {
dp[u] = make_pair(0, 0);
int cnt = 0;
sort(adj[u].begin(), adj[u].end(), [&] (const int &x, const int &y) {
return e[x].get(u) < e[y].get(u);
});
for (int i : adj[u]) if(e[i].get(u) != p) {
int v = e[i].get(u);
par[v] = i;
dfs(v, u);
if(cnt == 0) {
dp[u].fi = max(dp[v].fi, dp[v].se) + e[i].w;
assert((u << 1) == v);
} else {
dp[u].se = max(dp[v].fi, dp[v].se) + e[i].w;
assert((u << 1 | 1) == v);
}
++cnt;
}
}
void solve() {
dfs(1, 0);
segment_tree <ll, op, E> it(n);
for (int i = 1; i <= n; ++i) it.set(i, dp[i].fi + dp[i].se);
ll last = 0;
while(q--) {
int d; ll f; cin >> d >> f;
d = (d + last % (n - 1)) % (n - 1) + 1;
f = (f + last) % W;
e[d].w = f;
int u = e[d].v;
while(u != 1) {
int p = e[par[u]].get(u);
if((p << 1 | 1) == u) {
dp[p].se = max(dp[u].fi, dp[u].se) + e[par[u]].w;
} else {
assert((p << 1) == u);
dp[p].fi = max(dp[u].fi, dp[u].se) + e[par[u]].w;
}
u = p;
it.set(u, dp[u].fi + dp[u].se);
}
last = it.get(1, n);
cout << last << '\n';
}
exit(0);
}
}
void you_make_it(void) {
cin >> n >> q >> W;
for (int i = 1; i < n; ++i) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back(i);
adj[v].push_back(i);
e[i] = Edge(u, v, w);
}
if(sub4::check()) sub4::solve();
if(sub3::check()) sub3::solve();
if(sub12::check()) sub12::solve();
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
file("diameter");
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
you_make_it();
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
Compilation message (stderr)
diameter.cpp: In instantiation of 'sub3::segment_tree<T, f, e>::segment_tree(long long int) [with T = std::pair<long long int, long long int>; T (* f)(T, T) = sub3::_max_; T (* e)() = sub3::E]':
diameter.cpp:125:52: required from here
diameter.cpp:83:13: warning: 'sub3::segment_tree<std::pair<long long int, long long int>, sub3::_max_, sub3::E>::n' will be initialized after [-Wreorder]
83 | int n;
| ^
diameter.cpp:82:20: warning: 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > > sub3::segment_tree<std::pair<long long int, long long int>, sub3::_max_, sub3::E>::it' [-Wreorder]
82 | vector <T> it;
| ^~
diameter.cpp:110:9: warning: when initialized here [-Wreorder]
110 | segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
| ^~~~~~~~~~~~
diameter.cpp: In instantiation of 'sub4::segment_tree<T, f, e>::segment_tree(long long int) [with T = long long int; T (* f)(T, T) = sub4::op; T (* e)() = sub4::E]':
diameter.cpp:222:38: required from here
diameter.cpp:156:13: warning: 'sub4::segment_tree<long long int, sub4::op, sub4::E>::n' will be initialized after [-Wreorder]
156 | int n;
| ^
diameter.cpp:155:20: warning: 'std::vector<long long int> sub4::segment_tree<long long int, sub4::op, sub4::E>::it' [-Wreorder]
155 | vector <T> it;
| ^~
diameter.cpp:179:9: warning: when initialized here [-Wreorder]
179 | segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
| ^~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:269:5: note: in expansion of macro 'file'
269 | file("diameter");
| ^~~~
diameter.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:269:5: note: in expansion of macro 'file'
269 | file("diameter");
| ^~~~
# | 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... |