前言
题目链接：洛谷 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;
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
