제출 #1337408

#제출 시각아이디문제언어결과실행 시간메모리
1337408nguyenkhangninh99Dynamic Diameter (CEOI19_diameter)C++20
100 / 100
268 ms46024 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 2e5 + 5;
struct node{
	int ans, mnsuf, mxpre, fsuf, fpre, fsum, sum;
} st[4 * maxn];
node merge(node a, node b){
    return {max({a.ans, b.ans, -a.mnsuf + b.fpre, a.fsuf + b.mxpre}), min(b.mnsuf, b.sum + a.mnsuf), max(a.mxpre, a.sum + b.mxpre), max({-a.mnsuf + b.fsum, b.fsuf, a.fsuf + b.sum}), max({a.fsum + b.mxpre, a.fpre, -a.sum + b.fpre}), max({-a.sum + b.sum, -a.sum + b.fsum, a.fsum + b.sum}), a.sum + b.sum};
}
void update(int id, int l, int r, int p, int val){
	if(l == r) st[id] = {abs(val),val,val,abs(val),abs(val),abs(val),val};
    else{
        int mid = (l + r) / 2;
        if(p <= mid) update(id * 2, l, mid, p, val);
        else update(id * 2 + 1, mid + 1, r, p, val);
        st[id] = merge(st[id * 2], st[id * 2 + 1]);
    }
}
vector<array<int, 2>> g[maxn];
int tin[maxn], out[maxn], timedfs;
int pos[maxn], len[maxn];
void dfs(int u, int p){
	tin[u] = ++timedfs;
	for(auto [v, id]: g[u]){
        if(v == p) continue;
        pos[id] = v;
        dfs(v, u);
	}
	out[u] = ++timedfs;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, q, w; cin >> n >> q >> w;

	for(int i = 1; i <= n - 1; i++){
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
        len[i] = c;
	}
	dfs(1, 1);
	for(int i = 1; i <= n - 1; i++){
		update(1, 1, n * 2, tin[pos[i]], len[i]);
		update(1, 1, n * 2, out[pos[i]],-len[i]);
	}
	int last = 0;
	while(q--){
		int d, e; cin >> d >> e;
		d = (d + last) % (n - 1) + 1;
        e = (e + last) % w;

		update(1, 1, n * 2, tin[pos[d]], e);
		update(1, 1, n * 2, out[pos[d]],-e);
		cout << (st[1].ans) << "\n";
        last = st[1].ans;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...