树链剖分 | 洛谷 P4114 Qtree1

2023-08-20 18:52 由 Heartquakes 发表于 #其他

前言

题目链接：洛谷 P4114 Qtree1

前置知识：树链剖分

题意

给定一棵树，有修改边权和查询两点之间边权最大值两种操作，对于每个查询输出结果。

解析

已经在前置博客里提到，树链剖分 可以将树上的任意一条路径划分成不超过 \(O(\log n)\) 条连续的链，保证划分出的每条链上的节点 DFS 序 连续。这大大方便了我们维护点权，但该如何维护边权呢？

这里就要介绍一种重要的思想——化边权为点权。

从 \(1\) 号点开始，遍历一遍整棵树，对于每条边，把边权赋在后遍历到的那个点，也就是 \(dep\) 更大的点上。这样可以保证，在跳祖先的过程中，必然能够不重不漏地计算到每个边权。若把边权赋在 \(dep\) 更大的点上则不然。最后就是简单的 树剖+线段树 维护最大值的过程。

查询操作不用多说，就是树剖的常规操作，不断跳祖先查询最大值即可。

修改操作就比较复杂了，要找到第 \(i\) 条边上 \(dep\) 较大的点（因为边权存在这个点上），然后使用线段树单点修改。

这里要注意，使用 链式前向星 存图会比 vector 邻接表方便更多，因为我们要找到输入的第 \(i\) 条边。

代码

// Problem: P4114 Qtree1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4114
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 100005;
int n, u, v, w, cnt, tot, a, b;
int head[N], top[N], dep[N], dfn[N], heavy[N], son[N], val[N], f[N];
string s;

struct edge
{
	int from, to, val, nxt;
}e[N << 1];

inline void add_edge(int u, int v, int w)
{
	e[++tot] = {u, v, w, head[u]}, head[u] = tot;
}

inline void dfs1(int u, int fa)
{
	dep[u] = dep[fa] + 1, f[u] = fa, son[u] = 1;
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if(v == fa) continue;
		dfs1(v, u);
		son[u] += son[v];
		if(son[heavy[u]] <= son[v]) heavy[u] = v;
	}
	return;
}

inline void dfs2(int u, int tp)
{
	top[u] = tp, dfn[u] = ++cnt;
	if(!heavy[u]) return;
	dfs2(heavy[u], tp);
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if(v == f[u] || v == heavy[u]) continue;
		dfs2(v, v);
	}
	return;
}

struct node
{
	int l, r, maxi;
}tree[N << 2];

inline void push_up(int x)
{
	tree[x].maxi = max(tree[x << 1].maxi, tree[x << 1 | 1].maxi);	
}

inline void build(int l, int r, int x)
{
	tree[x] = {l, r, 0};
	if(l == r) return (void) (tree[x].maxi = val[l]);
	int mid = l + r >> 1;
	build(l, mid, x << 1);
	build(mid + 1, r, x << 1 | 1);
	push_up(x);
	return;
}

inline void update(int pos, int k, int x)
{
	if(tree[x].l == tree[x].r && tree[x].r == pos)
		return (void) (tree[x].maxi = k);
	int mid = tree[x].l + tree[x].r >> 1;
	if(pos <= mid) update(pos, k, x << 1);
	if(pos > mid) update(pos, k, x << 1 | 1);
	push_up(x);
	return;
}

inline int query(int l, int r, int x)
{
	if(l <= tree[x].l && tree[x].r <= r) return tree[x].maxi;
	int mid = tree[x].l + tree[x].r >> 1, ans = 0;
	if(l <= mid) ans = max(ans, query(l, r, x << 1));
	if(r > mid) ans = max(ans, query(l, r, x << 1 | 1));
	return ans;
}

inline int ask(int x, int y)
{
	int ans = 0;
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		ans = max(ans, query(dfn[top[x]], dfn[x], 1));
		x = f[top[x]];
	}
	if(dfn[x] > dfn[y]) swap(x, y);
	return max(ans, query(dfn[x] + 1, dfn[y], 1));
}

signed main()
{
	ios :: sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i < n; i++)
	{
		cin >> u >> v >> w;
		add_edge(u, v, w);
		add_edge(v, u, w);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	for(int i = 1; i <= tot; i += 2)
	{
		int u = e[i].from, v = e[i].to;
		if(dep[u] < dep[v]) swap(u, v);
		val[dfn[u]] = e[i].val;
	}
	build(1, n, 1);
	while(cin >> s)
	{
		if(s == "DONE") break;
		cin >> a >> b;
		if(s == "CHANGE")
		{
			a = a * 2 - 1;
			int u = e[a].from, v = e[a].to;
			if(dep[u] < dep[v]) swap(u, v);
			update(dfn[u], b, 1);
		}
		else cout << (a == b ? 0 : ask(a, b)) << '\n';
	}
	return 0;
}