#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
using namespace std;
const int mxN = 1227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
struct IT{
int n;
vector<ll> t;
vector<ll> lz;
IT(){}
IT(int _n) {
n = _n;
t.resize(n * 4 + 7, 0);
lz.resize(n * 4 + 7, 0);
}
void push_down(int v)
{
for(int i = v * 2; i <= v * 2 + 1; i++) {
t[i] += lz[v];
lz[i] += lz[v];
}
lz[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, ll val)
{
if(l > r) return;
if(tl == l && tr == r) {
t[v] += val;
lz[v] += val;
}
else {
push_down(v);
int tm = (tl + tr) / 2;
update(v * 2, tl, tm, l, min(r, tm), val);
update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
ll getmax(int v, int tl, int tr, int l, int r)
{
if(l > r) return 0;
if(tl == l && tr == r) return t[v];
push_down(v);
int tm = (tl + tr) / 2;
ll m1 = getmax(v * 2, tl, tm, l, min(r, tm));
ll m2 = getmax(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
return max(m1, m2);
}
void update(int l, int r, ll val)
{
update(1, 1, n, l, r, val);
}
ll getmax(int l, int r)
{
return getmax(1, 1, n, l, r);
}
} seg[mxN];
struct ITmax{
int n;
vector<ll> t;
ITmax(){}
ITmax(int _n) {
n = _n;
t.resize(n * 4 + 7, 0);
}
void update(int v, int tl, int tr, int pos, ll val)
{
if(tl == tr) t[v] = val;
else {
int tm = (tl + tr) / 2;
if(pos <= tm) update(v * 2, tl, tm, pos, val);
else update(v * 2 + 1, tm + 1, tr, pos, val);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
ll getmax(int v, int tl, int tr, int l, int r)
{
if(l > r) return 0;
if(tl == l && tr == r) return t[v];
int tm = (tl + tr) / 2;
ll m1 = getmax(v * 2, tl, tm, l, min(r, tm));
ll m2 = getmax(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
return max(m1, m2);
}
void update(int pos, ll val)
{
update(1, 1, n, pos, val);
}
ll getmax(int l, int r)
{
return getmax(1, 1, n, l, r);
}
} maxval;
struct EDGE{
int u, v;
ll c;
} ed[mxN];
int n;
int q;
ll lim;
int sub[mxN];
int par[mxN];
bool removed[mxN];
vector<pair<int, ll>> adj[mxN];
map<int, int> sta[mxN];
map<int, int> fin[mxN];
map<int, int> part[mxN];
map<int, ll> dist[mxN];
multiset<pair<ll, int>> ms[mxN];
int timer = 0;
void dfs_sz(int u, int p)
{
sub[u] = 1;
for(auto it : adj[u]) {
int v = it.fi;
if(v == p || removed[v] == true) continue;
dfs_sz(v, u);
sub[u] += sub[v];
}
}
int find_centroid(int u, int p, int n)
{
for(auto it : adj[u]) {
int v = it.fi;
if(v == p || removed[v] == true) continue;
if(sub[v] > n / 2) return find_centroid(v, u, n);
}
return u;
}
void dfs(int u, int p, int root, ll cur, int group)
{
part[root][u] = group;
dist[root][u] = cur;
sta[root][u] = ++timer;
seg[root].update(timer, timer, cur);
for(auto it : adj[u]) {
int v = it.fi;
ll c = it.se;
if(v == p || removed[v] == true) continue;
if(u == root) dfs(v, u, root, cur + c, v);
else dfs(v, u, root, cur + c, group);
}
fin[root][u] = timer;
}
void update_maxval(int p)
{
ll val = 0;
if(sz(ms[p]) == 1) {
pair<ll, int> tmp = *ms[p].begin();
val = tmp.fi;
}
if(sz(ms[p]) > 1) {
auto it = ms[p].end();
--it;
pair<ll, int> tmp;
tmp = *it;
val += tmp.fi;
--it;
tmp = *it;
val += tmp.fi;
}
// cout << p << ' ' << val << endl;
maxval.update(p, val);
}
void init_centroid(int u, int p)
{
timer = 0;
dfs_sz(u, -1);
int c = find_centroid(u, -1, sub[u]);
par[c] = p;
seg[c] = IT(sub[u]);
dfs(c, -1, c, 0, 0);
for(auto it : adj[c]) {
int v = it.fi;
if(removed[v] == false) {
int l = sta[c][v];
int r = fin[c][v];
ll val = seg[c].getmax(l, r);
ms[c].insert(make_pair(val, v));
}
}
update_maxval(c);
removed[c] = true;
for(auto it : adj[c]) {
int v = it.fi;
if(removed[v] == true) continue;;
init_centroid(v, c);
}
}
void update(int u, int v, ll w)
{
set<int> node;
int x = u;
int y = v;
while(x != -1) {
node.insert(x);
x = par[x];
if(sta[x].count(u) == 0 || sta[x].count(v) == 0 || fin[x].count(u) == 0 || fin[x].count(v) == 0) continue;
int lu = sta[x][u];
int ru = fin[x][u];
int lv = sta[x][v];
int rv = fin[x][v];
if(lu <= lv && rv <= ru) {
int cc = part[x][v];
ll val = seg[x].getmax(sta[x][cc], fin[x][cc]);
ms[x].erase(ms[x].find(make_pair(val, cc)));
seg[x].update(lv, rv, w);
val = seg[x].getmax(sta[x][cc], fin[x][cc]);
ms[x].insert(make_pair(val, cc));
}
if(lv <= lu && ru <= rv) {
int cc = part[x][u];
ll val = seg[x].getmax(sta[x][cc], fin[x][cc]);
ms[x].erase(ms[x].find(make_pair(val, cc)));
seg[x].update(lu, ru, w);
val = seg[x].getmax(sta[x][cc], fin[x][cc]);
ms[x].insert(make_pair(val, cc));
}
update_maxval(x);
}
while(y != -1) {
if(node.find(y) != node.end()) break;
// cerr << y << endl;
y = par[y];
if(sta[y].count(u) == 0 || sta[y].count(v) == 0 || fin[y].count(u) == 0 || fin[y].count(v) == 0) continue;
int lu = sta[y][u];
int ru = fin[y][u];
int lv = sta[y][v];
int rv = fin[y][v];
if(lu <= lv && rv <= ru) {
int cc = part[y][v];
ll val = seg[y].getmax(sta[y][cc], fin[y][cc]);
ms[y].erase(ms[y].find(make_pair(val, cc)));
seg[y].update(lv, rv, w);
val = seg[y].getmax(sta[y][cc], fin[y][cc]);
ms[y].insert(make_pair(val, cc));
}
if(lv <= lu && ru <= rv) {
int cc = part[y][u];
ll val = seg[y].getmax(sta[y][cc], fin[y][cc]);
ms[y].erase(ms[y].find(make_pair(val, cc)));
seg[y].update(lu, ru, w);
val = seg[y].getmax(sta[y][cc], fin[y][cc]);
ms[y].insert(make_pair(val, cc));
}
update_maxval(y);
}
}
void solve()
{
cin >> n >> q >> lim;
for(int i = 1; i < n; i++) {
int u, v;
ll c;
cin >> u >> v >> c;
adj[u].pb({v, c});
adj[v].pb({u, c});
ed[i] = {u, v, c};
}
maxval = ITmax(n);
init_centroid(1, -1);
// cout << maxval.getmax(1, n) << endl;
// return;
ll last = 0;
while(q--) {
ll idx;
ll w;
cin >> idx >> w;
idx = (idx + last) % (n - 1);
w = (w + last) % lim;
// cout << idx << ' ' << w << endl;
update(ed[idx + 1].u, ed[idx + 1].v, w - ed[idx + 1].c);
ed[idx + 1].c = w;
// update(ed[idx + 1].u, ed[idx + 1].v, ed[idx + 1].c);
last = maxval.getmax(1, n);
cout << last << endl;
}
// for(int i = 1; i < n; i++) cout << ed[i].u << ' ' << ed[i].v << ' ' << ed[i].c << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen(TASK".inp" , "r" , stdin);
// freopen(TASK".out" , "w" , stdout);
int tc = 1;
//cin >> tc;
while(tc--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5071 ms |
596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5071 ms |
596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5099 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5092 ms |
3028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1236 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5071 ms |
596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
