前言

题目链接：洛谷 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 
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;
	build(l, mid, x > 1;
	if(pos  mid) update(pos, k, x > 1, ans = 0;
	if(l  mid) ans = max(ans, query(l, r, 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 > u >> v >> w;
		add_edge(u, v, w);
		add_edge(v, u, w);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	for(int i = 1; i > 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] 

机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net