Codeforces 1192B 全dfs序 + 线段树

小咪咪 2023-08-17 17:22 109阅读 0赞

题意：给你一颗树，每次会修改一条边的边权，问修改之后的树的直径是多少？

思路：来源于：[https://www.cnblogs.com/TinyWong/p/11260601.html][https_www.cnblogs.com_TinyWong_p_11260601.html]

得到树的全序dfs序之后，我们考虑用线段树维护x - 2 \* y + z。维护方法和2017, 2016那道题差不多，对于每个区间维护:x, -y, z, x - 2 \* y, -2 \* y + z, x - 2 \* y + z6个部分的最大值，然后区间合并。

代码：

#include <bits/stdc++.h>
    #define ls (o << 1)
    #define rs (o << 1 | 1)
    #define LL long long
    #define INF 1e18
    using namespace std;
    const int maxn = 100010;
    int lp[maxn], rp[maxn], mp[maxn * 2], tot;
    vector<pair<int, long long> > G[maxn];
    LL d[maxn];
    void add(LL x, LL y, LL z) {
    	G[x].push_back(make_pair(y, z));
    	G[y].push_back(make_pair(x, z));
    }
    struct edge {
    	int u, v;
    	LL w;
    };
    edge a[maxn];
    struct Seg {
    	LL v[6], lz;
    	//0: a
    	//1: b
    	//2: c
    	//3: a + 2 * b
    	//4: 2 * c + b
    	//5: a + b + 2 * c
    };
    Seg tr[maxn * 8];
    void pushup(int o) {
    	//0:
    	tr[o].v[0] = max(tr[ls].v[0], tr[rs].v[0]);
    	//1:
    	tr[o].v[1] = max(tr[ls].v[1], tr[rs].v[1]);
    	//2:
    	tr[o].v[2] = max(tr[ls].v[2], tr[rs].v[2]);
    	//3:
    	tr[o].v[3] = max(tr[ls].v[3], tr[rs].v[3]);
    	tr[o].v[3] = max(tr[o].v[3], tr[ls].v[0] + 2ll * tr[rs].v[1]);
    	//4:
    	tr[o].v[4] = max(tr[ls].v[4], tr[rs].v[4]);
    	tr[o].v[4] = max(tr[o].v[4], 2ll * tr[ls].v[1] + tr[rs].v[2]);
    	//: 5
    	tr[o].v[5] = max(tr[ls].v[5], tr[rs].v[5]);
    	tr[o].v[5] = max(tr[o].v[5], tr[ls].v[3] + tr[rs].v[2]);
    	tr[o].v[5] = max(tr[o].v[5], tr[ls].v[0] + tr[rs].v[4]);
    }
    void maintain(int o, LL x) {
    	tr[o].lz += x;
    	tr[o].v[0] += x;
    	tr[o].v[1] -= x;
    	tr[o].v[2] += x;
    	tr[o].v[3] -= x;
    	tr[o].v[4] -= x;
    }
    void pushdown(int o) {
    	if(tr[o].lz) {
    		maintain(ls, tr[o].lz);
    		maintain(rs, tr[o].lz);
    		tr[o].lz = 0;
    	} 
    }
    void build(int o, int l, int r) {
    	tr[o].lz = 0;
    	if(l == r) {
    		tr[o].v[0] = tr[o].v[2] = d[mp[l]];
    		tr[o].v[4] = tr[o].v[3] = tr[o].v[1] = -d[mp[l]];
    		tr[o].v[5] = 0; 
    		return;
    	}
    	int mid = (l + r) >> 1;
    	build(ls, l, mid);
    	build(rs, mid + 1, r);
    	pushup(o);
    }
    void update(int o, int l, int r, int ql, int qr, LL val) {
    	if(l >= ql && r <= qr) {
    		maintain(o, val);
    		return;
    	}
    	int mid = (l + r) >> 1;
    	pushdown(o);
    	if(ql <= mid) update(ls, l, mid, ql, qr, val);
    	if(qr > mid) update(rs, mid + 1, r, ql, qr, val);
    	pushup(o);
    }
    void dfs(int x, int fa, LL dis) {
    	mp[++tot] = x;
    	lp[x] = tot;
    	rp[x] = tot;
    	d[x] = dis;
    	for (auto y : G[x]) {
    		if(y.first == fa) continue;
    		dfs(y.first, x, dis + y.second);
    		mp[++tot] = x;
    		rp[x] = tot;
    	}
    }
    int main() {
    	int n, m;
    	LL w, x, y, z;
    	scanf("%d%d%lld", &n, &m, &w);
    	for (int i = 1; i < n; i++) {
    		scanf("%lld%lld%lld", &x, &y, &z);
    		add(x, y, z);
    		a[i].u = x, a[i].v = y, a[i].w = z;
    	}
    	dfs(1, 0, 0);
    	build(1, 1, tot);
    	LL ans = 0;
    	while(m--) {
    		scanf("%lld%lld", &x, &y);
    		x = (x + ans) % (n - 1) + 1;
    		y = (y + ans) % w;
    		int p;
    		if(lp[a[x].u] < lp[a[x].v]) p = a[x].v;
    		else p = a[x].u;
    		update(1, 1, tot, lp[p], rp[p], y - a[x].w);
    		a[x].w = y;
    		ans = tr[1].v[5];
    		printf("%lld\n", ans);
    	}
    }

转载于:https://www.cnblogs.com/pkgunboat/p/11551616.html

[https_www.cnblogs.com_TinyWong_p_11260601.html]: https://www.cnblogs.com/TinyWong/p/11260601.html