月下“毛景树”
题目背景
毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。
题目描述
爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有 $N$ 个节点和 $N-1$ 条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：
Change k w：将第k条树枝上毛毛果的个数改变为 $w$ 个。Cover u v w：将节点 $u$ 与节点 $v$ 之间的树枝上毛毛果的个数都改变为 $w$ 个。Add u v w：将节点 $u$ 与节点 $v$ 之间的树枝上毛毛果的个数都增加 $w$ 个。
由于毛毛虫很贪，于是他会有如下询问：
Max u v：询问节点 $u$ 与节点 $v$ 之间树枝上毛毛果个数最多有多少个。
输入格式
第一行一个正整数 $N$。
接下来 $N-1$ 行，每行三个正整数 $U_i,V_i$ 和 $W_i$，第 $i+1$ 行描述第 $i$ 条树枝。表示第 $i$ 条树枝连接节点 $U_i$ 和节点 $V_i$，树枝上有 $W_i$ 个毛毛果。 接下来是操作和询问，以 Stop 结束。
输出格式
对于毛毛虫的每个询问操作，输出一个答案。
样例 #1
样例输入 #1
4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop样例输出 #1
9
16提示
对于全部数据，$1\le N\le 10^5$，操作和询问数目不超过 $10^5$。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过 $10^9$ 个。
题解
这道题和正常树剖不一样的是我们需要维护边上的信息而不是节点上的信息，我们可以做一个小转化，我们把父亲节点连到子节点的边的边权转成子节点的点权，这样n-1条边的边权就被存到了除根节点外的所有节点上了。
题目中有一个推平操作和加操作，因此我们的线段树要处理区间推平和加，直接两个打lazytag就行，要注意的是标记下放的时候先下放推平的tag，不然推平操作会把加操作覆盖掉。
最后在树剖的时候，假如我们求x节点和y节点毛毛果最大值时，我们发现最后答案会将x，y的lca统计进答案，但是我们存边的时候lca(x,y)的存的边不应该在答案里。所以最后操作的时候我们将id[x]变为id[son[x]]就行，如果最后xy深度一样说明当前节点就是lca，直接return就行。
代码实现
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
#define root 1, n, 1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define endl '\n'
const int maxn = 100005;
int z[maxn << 2], tag[maxn << 2], ctag[maxn << 2], n;
int fa[maxn], son[maxn], dep[maxn], siz[maxn], id[maxn], rnk[maxn], top[maxn];
int cnt = 0;
struct node
{
int from;
int to;
int next;
int data;
} edge[maxn << 1];
int head[maxn], num;
inline void add_edge(int from, int to, int data)
{
edge[++num] = {from, to, head[from], data};
head[from] = num;
}
void dfs1(int now, int f, int deep)
{
fa[now] = f;
dep[now] = deep;
siz[now] = 1;
int maxson = -1;
for (int i = head[now], to; i; i = edge[i].next)
{
to = edge[i].to;
if (to != f)
{
dfs1(to, now, deep + 1);
siz[now] += siz[to];
if (siz[to] > maxson)
{
maxson = siz[to];
son[now] = to;
}
}
}
}
void dfs2(int now, int t, int v)
{
id[now] = ++cnt; // 点的编号映射
rnk[cnt] = v;
top[now] = t;
if (son[now] == 0)
return;
for (int i = head[now], to; i; i = edge[i].next)
{
to = edge[i].to;
if (to == son[now])
dfs2(to, t, edge[i].data);
}
for (int i = head[now], to; i; i = edge[i].next)
{
to = edge[i].to;
if (to != son[now] && to != fa[now])
dfs2(to, to, edge[i].data);
}
}
inline void update(int rt)
{
z[rt] = max(z[rt << 1], z[rt << 1 | 1]);
}
void build(int l, int r, int rt)
{
ctag[rt] = -1;
if (l == r)
{
z[rt] = rnk[l];
return;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
update(rt);
}
// 添加懒标记
inline void add_tag(int rt, int x)
{
z[rt] += x;
tag[rt] += x;
}
inline void add_cover_tag(int rt, int x)
{
z[rt] = x;
ctag[rt] = x;
tag[rt] = 0;
}
// 下传懒标记
inline void push_down(int rt)
{
if (ctag[rt] != -1) // 下放推平标记
{
add_cover_tag(rt << 1, ctag[rt]);
add_cover_tag(rt << 1 | 1, ctag[rt]);
ctag[rt] = -1;
}
if (tag[rt] != 0) // 下放加减标记
{
add_tag(rt << 1, tag[rt]);
add_tag(rt << 1 | 1, tag[rt]);
tag[rt] = 0;
}
}
// 线段树区间修改
void modify(int l, int r, int rt, int findl, int findr, int x)
{
if (l == findl && r == findr)
{
add_tag(rt, x);
return;
}
push_down(rt);
int mid = (l + r) >> 1;
if (findl <= mid)
{
if (findr > mid)
{
modify(lson, findl, mid, x);
modify(rson, mid + 1, findr, x);
}
else
modify(lson, findl, findr, x);
}
else
modify(rson, findl, findr, x);
update(rt);
}
void cover(int l, int r, int rt, int findl, int findr, int x)
{
if (l == findl && r == findr)
{
add_cover_tag(rt, x);
return;
}
push_down(rt);
int mid = (l + r) >> 1;
if (findl <= mid)
{
if (findr > mid)
{
cover(lson, findl, mid, x);
cover(rson, mid + 1, findr, x);
}
else
cover(lson, findl, findr, x);
}
else
cover(rson, findl, findr, x);
update(rt);
}
int query(int l, int r, int rt, int findl, int findr)
{
if (l == findl && r == findr)
return z[rt];
int mid = (l + r) >> 1;
push_down(rt);
if (findl <= mid)
{
if (findr > mid)
return max(query(lson, findl, mid), query(rson, mid + 1, findr));
return query(lson, findl, findr);
}
return query(rson, findl, findr);
}
// 树链剖分修改
inline void tree_modify(int x, int y, int z)
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
swap(x, y);
modify(root, id[top[x]], id[x], z);
x = fa[top[x]];
}
if (dep[x] == dep[y])
return;
if (dep[x] > dep[y])
swap(x, y);
modify(root, id[son[x]], id[y], z);
}
inline void tree_cover(int x, int y, int z)
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
swap(x, y);
cover(root, id[top[x]], id[x], z);
x = fa[top[x]];
}
if (dep[x] == dep[y])
return;
if (dep[x] > dep[y])
swap(x, y);
cover(root, id[son[x]], id[y], z);
}
inline int tree_query(int x, int y)
{
int ans = -1;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
swap(x, y);
ans = max(ans, query(root, id[top[x]], id[x]));
x = fa[top[x]];
}
if (dep[x] == dep[y])
return ans;
if (dep[x] > dep[y])
swap(x, y);
ans = max(ans, query(root, id[son[x]], id[y]));
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1, x, y, w; i < n; i++)
{
cin >> x >> y >> w;
add_edge(x, y, w);
add_edge(y, x, w);
}
dfs1(1, 1, 1);
dfs2(1, 1, 0);
build(root);
string cmd;
int x, y, z;
while (true)
{
cin >> cmd;
if (cmd == "Max")
{
cin >> x >> y;
cout << tree_query(x, y) << endl;
}
else if (cmd == "Cover")
{
cin >> x >> y >> z;
tree_cover(x, y, z);
}
else if (cmd == "Change")
{
cin >> x >> y;
tree_cover(edge[x << 1].from, edge[x << 1].to, y);
}
else if (cmd == "Add")
{
cin >> x >> y >> z;
tree_modify(x, y, z);
}
else
break;
}
return 0;
}总结
本题是一道比较典型的树链剖分和线段树的综合应用题目。通过本题的练习，我们可以更加深入地理解树链剖分和线段树的原理和应用。
Comments NOTHING