Submission #1234217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234217		g4yuhg	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	1028 ms	60996 KiB

diameter

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define int long long
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1000000000000000000LL
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 100005
using namespace std;

bool ghuy4g;

ll S = 317;

struct Canh {
    int u, v; long long w;
} canh[N];

ll n, t, q, w;
vector<pii> adj[N];
int st[LOG + 2][2 * N], L[N], R[N], id[N];
int in[N], tour[N], high[N], par[N], out[N], timeDfs;
vector<ll> euler, depth, first;
ll d[N], lazy[N];

void dfs(ll u, ll parent, ll di) {
	in[u] = ++ timeDfs;
	tour[timeDfs] = u;
    first[u] = euler.size();
    euler.push_back(u);
    depth.push_back(di);
    for (auto v : adj[u]) {
        if (v.fi == parent) continue;
        par[v.fi] = u;
        dfs(v.fi, u, di + 1);
        euler.push_back(u);
        depth.push_back(di);
    }
    out[u] = timeDfs;
}

void build_sparse_table() {
    ll m = depth.size();
    for (ll i = 0; i < m; ++i) {
        st[0][i] = i; // store index in depth[]
    }
    for (ll k = 1; (1 << k) <= m; ++k) {
        for (ll i = 0; i + (1 << k) <= m; ++i) {
            ll x = st[k - 1][i];
            ll y = st[k - 1][i + (1 << (k - 1))];
            st[k][i] = (depth[x] < depth[y] ? x : y);
        }
    }
}
ll get_min_index(ll l, ll r) {
    ll len = r - l + 1;
    ll k = 31 - __builtin_clz(len); // floor(log2(len))
    ll x = st[k][l];
    ll y = st[k][r - (1 << k) + 1];
    return (depth[x] < depth[y] ? x : y);
}

ll lca(ll u, ll v) {
    ll l = first[u];
    ll r = first[v];
    if (l > r) swap(l, r);
    ll idx_in_depth = get_min_index(l, r);
    return euler[idx_in_depth];
}

ll query(ll u) {
    return d[ in[u] ] + lazy[ id[ in[u] ] ];
}

ll dis(ll u, ll v) {
	ll x = lca(u, v);
	return query(u) + query(v) - 2 * query(x);
}

struct Node {
	int u, v; long long len;
} ST[4 * N];

Node combine(Node A, Node B) {
    Node res = {0, 0, -inf};
    ll d;
    d = dis(A.u, A.v); if (d > res.len) res = {A.u, A.v, d};
    d = dis(A.u, B.u); if (d > res.len) res = {A.u, B.u, d};
    d = dis(A.u, B.v); if (d > res.len) res = {A.u, B.v, d};
    d = dis(A.v, B.u); if (d > res.len) res = {A.v, B.u, d};
    d = dis(A.v, B.v); if (d > res.len) res = {A.v, B.v, d};
    d = dis(B.u, B.v); if (d > res.len) res = {B.u, B.v, d};
    return res;
}

void Build(int id, int l, int r) {
    if (l == r) {
        ST[id] = {tour[l], tour[l], 0};
        return;
    }
    int mid = (l + r) >> 1;
    Build(id<<1, l, mid);
    Build(id<<1|1, mid+1, r);
    ST[id] = combine(ST[id<<1], ST[id<<1|1]);
}

void update1_rec(int id, int l, int r, int pos) {
	if (l > pos || r < pos) return;
    if (l == r) {
        ST[id] = {tour[l], tour[l], 0};
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update1_rec(id<<1, l, mid, pos);
    else            update1_rec(id<<1|1, mid+1, r, pos);
    ST[id] = combine(ST[id<<1], ST[id<<1|1]);
}

void update1(int pos) {
    update1_rec(1, 1, n, pos);
}

bool flag = 0;

void upd_sqrt(ll u, ll w) { // update subtree u them w ;// mang d la tinh theo tour, khi get ta lay d[tour[u]] voi u la dinh
	// in[u] -> out[u]
	// for tu in[u] -> cuoi block in[u]
	if (flag) {
		cout << u << " " << w << " " << in[u] << " " << out[u] << endl;
	}
	if (id[in[u]] == id[out[u]]) {
		for (int i = in[u]; i <= out[u]; i ++) {
			if (flag) cout << "trau cong0 " << i << " " << w << endl;
			d[i] += w;
		}
		return;
	}
	for (int i = in[u]; i <= R[id[in[u]]]; i ++) {
		//cout << "trau cong1 " << i << " " << w << endl;
		d[i] += w;
	}
	for (int i = L[id[out[u]]]; i <= out[u]; i ++) {
		//cout << "trau cong2 " << i << " " << w << endl;
		d[i] += w;
	}
	for (int i = id[in[u]] + 1; i <= id[out[u]] - 1; i ++) {
		//cout << "lazy cong " << i << " " << w << endl;
		lazy[i] += w;
	}
}

void upd(int i, ll val) {
    int u = canh[i].u, v = canh[i].v;
    if (par[u] == v) swap(u, v);
    
    upd_sqrt(v, val - canh[i].w);
    canh[i].w = val;
    //cout << v << endl;
    //cout << query(7) << endl;
    if (par[v] == u) swap(u, v); // u la con
    update1(in[u]); update1(in[u] - 1); update1(out[u]); update1(out[u] + 1);
}

void pre() {
	
	first.resize(n + 1);
    dfs(1, -1, 0);
    build_sparse_table();
    
    // prepare for chia can
    for (int i = 1; i <= n; i ++) {
    	id[i] = (i - 1) / S + 1;
    	if (L[id[i]] == 0) L[id[i]] = i;
    	R[id[i]] = i;
    	//cout << i << " " << in[i] << " " << out[i] << endl;
    }
    //cout << lca(2, 8) << endl;
    for (int i = 1; i <= n - 1; i ++) {
    	ll u = canh[i].u, v = canh[i].v, w = canh[i].w;
    	if (u == par[v]) swap(u, v);
    	upd_sqrt(u, w);
    	//cout << u << " uw " << w << endl;
    }
    
    Build(1, 1, n);
    //cout << query(1, 3) << endl;
    //cout << ST[1].len << endl;
    //cout << query(2) << endl;
    //cout << query(3) << endl;
    //cout << query(1) << endl;
    //exit(0);
}

void solve() {
	ll last = 0;
    for (int i = 1; i <= q; i ++) {
    	ll d, e;
    	cin >> d >> e;
    	d = (d + last) % (n - 1);
    	e = (e + last) % w;
    	d ++ ;
    	if (i == 97) {
    		//cout << last << " " << d << " " << e << " " << canh[d].w << endl;
    		//flag = 1;
    	}
    	upd(d, e);
    	cout << ST[1].len << endl;
    	last = ST[1].len;
    	flag = 0;
    }
}

bool klinh;

signed main(void) {
	faster;
	cin >> n >> q >> w;
	for (int i = 1; i <= n - 1; i ++) {
		ll u, v, w;
		cin >> u >> v >> w;
		canh[i] = {u, v, w};
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	
	pre();
	solve();
	
    
    cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27