#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll NMAX = 100002;
const ll INF = (1LL << 58);
const ll nrbits = 18;
const ll MOD = 998244353;
vector <int> v[NMAX];
pii diameter;
ll lung;
int dp[nrbits + 1][NMAX];
ll lazy[NMAX * 4];
pii aint[NMAX * 4];
pii timp[NMAX];
int stamp;
int n;
void propaga(int node, int st, int dr) {
if(st != dr) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
aint[node].first += lazy[node];
lazy[node] = 0;
}
pii combine(pii a, pii b) {
return max(a, b);
}
void update(int node, int st, int dr, int a, int b, ll val) {
propaga(node, st, dr);
if(a <= st && dr <= b) {
lazy[node] += val;
return;
}
int mid = (st + dr) / 2;
if(a <= mid)
update(node * 2, st, mid, a, b, val);
if(b > mid)
update(node * 2 + 1, mid + 1, dr, a, b, val);
propaga(node * 2, st, mid);
propaga(node * 2 + 1, mid + 1, dr);
aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}
pii query(int node, int st, int dr, int a, int b) {
propaga(node, st, dr);
if(a <= st && dr <= b) {
return aint[node];
}
int mid = (st + dr) / 2;
pii sol = {0, 0};
if(a <= mid) {
sol = combine(sol, query(node * 2, st, mid, a, b));
}
if(b > mid) {
sol = combine(sol, query(node * 2 + 1, mid + 1, dr, a, b));
}
return sol;
}
struct edge {
int a, b;
ll c;
} edges[NMAX];
int preorder[NMAX];
void build(int node, int st, int dr) {
if(st == dr) {
aint[node].second = preorder[st];
return;
}
int mid = (st + dr) / 2;
build(node * 2, st, mid);
build(node * 2 + 1, mid + 1, dr);
}
void DFS(int node, int p) {
timp[node].first = ++stamp;
preorder[stamp] = node;
dp[0][node] = p;
for(auto x : v[node]) {
if(x == p) continue;
DFS(x, node);
}
timp[node].second = stamp;
}
bool isParent(int a, int b) {
return timp[a].first <= timp[b].first && timp[b].second <= timp[a].second;
}
int LCA(int a, int b) {
int r = b, pas = nrbits;
while(pas >= 0) {
int nxt = dp[pas][r];
if(nxt != 0 && !isParent(nxt, a)) {
r = nxt;
}
pas--;
}
if(!isParent(r, a)) {
r = dp[0][r];
}
return r;
}
ll lgt(int a, int b) {
int lca = LCA(a, b);
return query(1, 1, n, timp[a].first, timp[a].first).first + query(1, 1, n, timp[b].first, timp[b].first).first - 2 * query(1, 1, n, timp[lca].first, timp[lca].first).first;
}
void extend(int i) {
pii initial = diameter;
// debugs(i);
int prim = lgt(diameter.first, i);
int sec = lgt(diameter.second, i);
//debugs(prim);
// debug(sec);
if(lung < prim) {
lung = prim;
diameter = {initial.first, i};
}
if(lung < sec) {
lung = sec;
diameter = {initial.second, i};
}
}
int main() {
#ifdef HOME
ifstream cin(".in");
ofstream cout(".out");
#endif // HOME
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int q, w, i;
cin >> n >> q >> w;
for(i = 1; i < n; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
v[a].push_back(b);
v[b].push_back(a);
edges[i] = {a, b, c};
}
DFS(1, 0);
for(int j = 1; j <= nrbits; j++) {
for(i = 1; i <= n; i++) {
dp[j][i] = dp[j - 1][dp[j - 1][i]];
}
}
build(1, 1, n);
for(i = 1; i < n; i++) {
if(dp[0][edges[i].a] == edges[i].b) {
swap(edges[i].a, edges[i].b);
}
update(1, 1, n, timp[edges[i].b].first, timp[edges[i].b].second, edges[i].c);
}
diameter = {1, 2};
lung = lgt(1, 2);
for(int j = 1; j <= n; j++) {
extend(j);
}
ll last = 0;
for(i = 1; i <= q; i++) {
ll a, b;
cin >> a >> b;
a += last;
a %= (n - 1);
b += last;
b %= w;
a++;
update(1, 1, n, timp[edges[a].b].first, timp[edges[a].b].second, b - edges[a].c);
edges[a].c = b;
lung = lgt(diameter.first, diameter.second);
int bst = query(1, 1, n, timp[edges[a].b].first, timp[edges[a].b].second).second;
extend(bst);
bst = query(1, 1, n, timp[edges[a].a].first, timp[edges[a].a].second).second;
extend(bst);
extend(1);
extend(edges[a].b);
extend(edges[a].a);
last = lung;
cout << lung << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
40136 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
