树链剖分 题型总结二

P1505 [国家集训队]旅游

https://www.luogu.org/problem/P1505
这道题 是边剖
我们要注意的是 我们的一条边上路权 可以分配给这条树下 深度较深的 节点上 边权转点权就好
而且 更要注意的是 我们的LCA 这个点的权不应该算入 因为他算上了 他父亲到他的路 所以这时候 idx[x] ＋ 1 跳过就好

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, k, m;
int head[maxn], sonw[maxn], cnt;
int to[maxn << 1], nxt[maxn << 1], val[maxn << 1];
pair<int, int> e[maxn];
void ade(int a, int b, int c) {
	to[++ cnt] = b, val[cnt] = c;
	nxt[cnt] = head[a], head[a] = cnt;
}

int fa[maxn], dep[maxn], siz[maxn], son[maxn];
void dfs1(int u, int f) {
	fa[u] = f;
	dep[u] = dep[f] + 1;
	siz[u] = 1;
	int maxsize = -1;
	for(int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == f) continue;
		sonw[v] = val[i];
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > maxsize) {
			maxsize = siz[v];
			son[u] = v;
		}
	}
}

int tim, dfn[maxn], top[maxn], w[maxn];
void dfs2(int u, int t) {
	dfn[u] = ++ tim;
	top[u] = t;
	w[tim] = sonw[u];
	if(!son[u]) return;
	dfs2(son[u], t);
	for(int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}

int tree[maxn << 2], lazy[maxn << 2], mi[maxn << 2], ma[maxn << 2];
void push_up(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
	ma[rt] = max(ma[rt << 1], ma[rt << 1 | 1]);
	mi[rt] = min(mi[rt << 1], mi[rt << 1 | 1]);
}
void push_down(int rt) {
	if(!lazy[rt]) return ;
	tree[rt << 1] = -tree[rt << 1], lazy[rt << 1] ^= 1;
	tree[rt << 1 | 1] = -tree[rt << 1 | 1] ,lazy[rt << 1 | 1] ^= 1;
	int t1 = ma[rt << 1], t2 = ma[rt << 1 | 1];
	int s1 = mi[rt << 1], s2 = mi[rt << 1 | 1];
	ma[rt << 1] = -s1, ma[rt << 1 | 1] = -s2;
	mi[rt << 1] = -t1, mi[rt << 1 | 1] = -t2;
	lazy[rt] = 0;
}

void build(int l, int r, int rt) {
	if(l == r) {
		tree[rt] = mi[rt] = ma[rt] = w[l];
		return ;
	}
	int mid = l + r >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	push_up(rt);
}

void updata(int L, int R, int l, int r, int rt) {
	if(L <= l && r <= R) {
		tree[rt] = -tree[rt], lazy[rt] ^= 1;
		int t = ma[rt], s = mi[rt];
		ma[rt] = -s, mi[rt] = -t;
		return ;
	}
	int mid = l + r >> 1;
	push_down(rt);
	if(L <= mid) updata(L, R, l, mid, rt << 1);
	if(R > mid) updata(L, R, mid + 1, r, rt << 1 | 1);
	push_up(rt);
}

void upd(int L, int l, int r, int rt, int val) {
	if(l == r) {
		tree[rt] = mi[rt] = ma[rt] = val;
		return ;
	}
	int mid = l + r >> 1;
	push_down(rt);
	if(L <= mid) upd(L, l, mid, rt << 1, val);
	else upd(L, mid + 1, r, rt << 1 | 1, val);
	push_up(rt);
}

int querysum(int L, int R, int l, int r, int rt) {
	if(L <= l && r <= R) {
		return tree[rt];
	}
	int mid = l + r >> 1;
	push_down(rt);
	int res = 0;
	if(L <= mid) res = (res + querysum(L, R, l, mid, rt << 1));
	if(R > mid) res = (res +querysum(L, R, mid + 1, r, rt << 1 | 1));
	return res;
}

int querymax(int L, int R, int l, int r, int rt) {
	if(L <= l && r <= R) {
		return ma[rt];
	}
	int mid = l + r >> 1;
	push_down(rt);
	int res = -0x3f3f3f3f;
	if(L <= mid) res = max(res, querymax(L, R, l, mid, rt << 1));
	if(R > mid) res = max(res, querymax(L, R, mid + 1, r, rt << 1 | 1));
	return res;
}

int querymin(int L, int R, int l, int r, int rt) {
	if(L <= l && r <= R) {
		return mi[rt];
	}
	int mid = l + r >> 1;
	push_down(rt);
	int res = 0x3f3f3f3f;
	if(L <= mid) res = min(res, querymin(L, R, l, mid, rt << 1));
	if(R > mid) res = min(res, querymin(L, R, mid + 1, r, rt << 1 | 1));
	return res;
}

void onlymson(int x, int z) {
	if(dep[e[x].first] > dep[e[x].second]) x = e[x].first;
	else x = e[x].second;
	upd(dfn[x], 1, n, 1, z);
}

void opp_mchain(int x, int y, int z = 1) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		updata(dfn[top[x]], dfn[x], 1, n, 1);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	updata(dfn[x] + 1, dfn[y], 1, n, 1);
}

int qchainsum(int x, int y) {
	int ret = 0;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		ret = (ret + querysum(dfn[top[x]], dfn[x], 1, n, 1));
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	ret = (ret + querysum(dfn[x] + 1, dfn[y], 1, n, 1));
	return ret;
}

int qchainmax(int x, int y) {
	int ret = -INF;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		ret = max(ret, querymax(dfn[top[x]], dfn[x], 1, n, 1));
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	ret = max(ret, querymax(dfn[x] + 1, dfn[y], 1, n, 1));
	return ret;
}

int qchainmin(int x, int y) {
	int ret = INF;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		ret = min(ret, querymin(dfn[top[x]], dfn[x], 1, n, 1));
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	ret = min(ret, querymin(dfn[x] + 1, dfn[y], 1, n, 1));
	return ret;
}

signed main() {
	scanf("%d", &n);
	for(int i = 1, a, b, c; i < n; i ++) {
		scanf("%d %d %d", &a, &b, &c);
		a ++, b ++;
		e[i] = make_pair(a, b);
		ade(a, b, c), ade(b, a, c);
	}
	dfs1(1, 0);
	dfs2(1, 0);
	build(1, n, 1);
	scanf("%d", &m);
	char op[15];
	int x, y;
	while(m --) {
		scanf("%s %d %d", op, &x, &y);
		x ++, y ++;
		if(op[0] == 'C') onlymson(x - 1, y - 1);
		if(op[0] == 'N') opp_mchain(x, y, -1);
		if(op[0] == 'S') printf("%d\n", qchainsum(x, y));
		if(op[1] == 'A') printf("%d\n", qchainmax(x, y));
		if(op[1] == 'I') printf("%d\n", qchainmin(x, y));
	}
	return 0;
}