月下“毛景树”
题目
click it!!
更好or更差的体验
思路
看完题目之后，很明显这是一道树剖题。为什么这么说呢？
- 他会改变树上两点的路径上的边权。
- 他要查询树上两点的路径上的最大边。
- 他要改变某条边的边权
从这几点来看就是说我们要在树上做区间操作！！！
这里有好多难点：
- 边权是很难使用的，不如将其改为点权
- 如何用树剖出的几条链组成的序列来进行各种操作
这里我们用线段树来进行区间操作，将边权改为“这条边的一个端点到另一个端点的所花费的值”（两个端点为父子节点的关系），这样就可以将边权化为点权。
比如：
代码
假设树剖之后我们用in[x]表示x这个点的dfs序，id[x]表示x这个编号对应的点（本人英语不好，数组名瞎取的）
之后我就直接给出线段树的操作代码:(别说你连线段树都不懂就来学树剖)
建树
void build(int c,int l,int r){
lazy[c]=-1;//当然要懒标记啊，这是初始化
if(l==r){
t[c]=a[l];
return;
}
int mid=(l+r)>>1;
build(c<<1,l,mid);
build(c<<1|1,mid+1,r);
t[c]=max(t[c<<1],t[c<<1|1]);//看上去是不是好简单啊，我就不说了
}下放懒标记
(注意：这里本人用了两个懒标记，一个是覆盖（lazy），一个是加（add）)
void spread(int c){
int ls=c<<1,rs=c<<1|1;//ls是左儿子，rs是右儿子
if(lazy[c]>=0){//如果有覆盖标记（覆盖优先）
add[ls]=add[rs]=0;//之前的add就为0了，被覆盖了
t[ls]=t[rs]=lazy[ls]=lazy[rs]=lazy[c];//下放lazy，并修改子区间的值
lazy[c]=-1;//清除标记
}
if(add[c]){//这太熟悉了，不说了
add[ls]+=add[c],add[rs]+=add[c];
t[ls]+=add[c],t[rs]+=add[c];
add[c]=0;
}
}区间加操作
void change1(int c,int l,int r,int x,int y,int k){
if(x<=l&&r<=y){
add[c]+=k; t[c]+=k;
return;
}
spread(c);
int mid=(l+r)>>1;
if(mid>=x) change1(c<<1,l,mid,x,y,k);
if(mid<y) change1(c<<1|1,mid+1,r,x,y,k);
t[c]=max(t[c<<1],t[c<<1|1]);
}//简单易懂，线段树基本操作区间覆盖
void change2(int c,int l,int r,int x,int y,int k){
if(x<=l&&r<=y){
t[c]=lazy[c]=k;
add[c]=0;
return;
}
spread(c);
int mid=(l+r)>>1;
if(mid>=x) change2(c<<1,l,mid,x,y,k);
if(mid<y) change2(c<<1|1,mid+1,r,x,y,k);
t[c]=max(t[c<<1],t[c<<1|1]);
}//不说了...区间查询最值
int query(int c,int l,int r,int x,int y){
if(x<=l&&r<=y) return t[c];
spread(c);
int mid=(l+r)>>1,maxx=0;
if(mid>=x) maxx=query(c<<1,l,mid,x,y);
if(mid<y) maxx=max(maxx,query(c<<1|1,mid+1,r,x,y));
return maxx;
}树上查询
（这是在树上查询，树剖的大作用就是这个，会详解）
int ask(int x,int y){
int maxx=0;
while(top[x]!=top[y]){//两个点当前不在一条重链上时，一条一条的跳到同一重链为止
if(dep[top[x]]<dep[top[y]]) swap(x,y);//深度深的先往上跳（有一点LCA的意思）
maxx=max(maxx,query(1,1,n,in[top[x]],in[x]));//这里要将x所在这条链上的值都查询好
//再将它与最终答案进行对比，记录答案
//为什么用线段树是放入的是in[top[x]]和in[x]呢？请大家想一想
//其实就是之前我们用树剖将树化为了一条序列（dfs序），序列中的in[top[x]]到in[x]就是树
//中的top[x]到x.
x=fa[top[x]];//这一条链已经操作完了，就跳到上一层链上
}
if(dep[x]>dep[y]) swap(x,y);//最后在同一条链时将x变为深度较深的点
//如果大家不懂，自己可以模拟一下dfs序中的x，y点的编号
maxx=max(maxx,query(1,1,n,in[x]+1,in[y]));//为什么in[x]要加1呢？
// 因为我们是边权化点权，最后一点是我们找到的父节点，但我们一直操作的是子节点
//若不懂，请大家模拟理解一下（模拟大法好啊！！！）
return maxx;
}还有两个树上修改
大家结合上面的修改看看吧（这不是我偷懒！！）
void DO1(int x,int y,int k){//树上加边权
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change1(1,1,n,in[top[x]],in[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
change1(1,1,n,in[x]+1,in[y],k);
}
void DO2(int x,int y,int k){//树上覆盖边权
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change2(1,1,n,in[top[x]],in[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
change2(1,1,n,in[x]+1,in[y],k);
}就是以上的几种操作，是不是好简单呢！！
当然，为什么我没写树剖要的那两个DFS呢，因为之前有写过了
这是链接
谢谢大家的阅读！！！！！！！！！！！！！！！！！！！！！
下面给出完整代码：
完整代码
（码风就不要在意了）
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,a[maxn],root,head[maxn],cnt,p[maxn];
int dep[maxn],fa[maxn],siz[maxn],son[maxn];
int top[maxn],tot,in[maxn];
int t[maxn<<2],add[maxn<<2],lazy[maxn<<2];
struct node{
int nxt,to,w;
}edge[maxn<<2];
void add_edge(int x,int y,int z){
edge[++cnt]=(node){head[x],y,z};
head[x]=cnt;
}
void dfs1(int x,int ffa){
fa[x]=ffa,siz[x]=1;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(y!=ffa){
dep[y]=dep[x]+1; p[y]=edge[i].w;
dfs1(y,x); siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
}
}
}
void dfs2(int x,int tp){
top[x]=tp,in[x]=++tot,a[tot]=p[x];
if(son[x]!=0) dfs2(son[x],tp);
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
}
}
void build(int c,int l,int r){
lazy[c]=-1;
if(l==r){
t[c]=a[l];
return;
}
int mid=(l+r)>>1;
build(c<<1,l,mid);
build(c<<1|1,mid+1,r);
t[c]=max(t[c<<1],t[c<<1|1]);
}
void spread(int c){
int ls=c<<1,rs=c<<1|1;
if(lazy[c]>=0){
add[ls]=add[rs]=0;
t[ls]=t[rs]=lazy[ls]=lazy[rs]=lazy[c];
lazy[c]=-1;
}
if(add[c]){
add[ls]+=add[c],add[rs]+=add[c];
t[ls]+=add[c],t[rs]+=add[c];
add[c]=0;
}
}
void change1(int c,int l,int r,int x,int y,int k){
if(x<=l&&r<=y){
add[c]+=k; t[c]+=k;
return;
}
spread(c);
int mid=(l+r)>>1;
if(mid>=x) change1(c<<1,l,mid,x,y,k);
if(mid<y) change1(c<<1|1,mid+1,r,x,y,k);
t[c]=max(t[c<<1],t[c<<1|1]);
}
void change2(int c,int l,int r,int x,int y,int k){
if(x<=l&&r<=y){
t[c]=lazy[c]=k;
add[c]=0;
return;
}
spread(c);
int mid=(l+r)>>1;
if(mid>=x) change2(c<<1,l,mid,x,y,k);
if(mid<y) change2(c<<1|1,mid+1,r,x,y,k);
t[c]=max(t[c<<1],t[c<<1|1]);
}
int query(int c,int l,int r,int x,int y){
if(x<=l&&r<=y) return t[c];
spread(c);
int mid=(l+r)>>1,maxx=0;
if(mid>=x) maxx=query(c<<1,l,mid,x,y);
if(mid<y) maxx=max(maxx,query(c<<1|1,mid+1,r,x,y));
return maxx;
}
int ask(int x,int y){
int maxx=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
maxx=max(maxx,query(1,1,n,in[top[x]],in[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
maxx=max(maxx,query(1,1,n,in[x]+1,in[y]));
return maxx;
}
void DO1(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change1(1,1,n,in[top[x]],in[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
change1(1,1,n,in[x]+1,in[y],k);
}
void DO2(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change2(1,1,n,in[top[x]],in[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
change2(1,1,n,in[x]+1,in[y],k);
}
int main(){
scanf("%d",&n);
int x,y,z;
for(int i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
add_edge(x,y,z),add_edge(y,x,z);
}
dep[1]=1; dfs1(1,0);
dfs2(1,1); build(1,1,n);
string s;
while(1){
cin>>s;
if(s=="Stop") break;
if(s=="Max"){
scanf("%d%d",&x,&y);
printf("%d\n",ask(x,y));
}
if(s=="Add"){
scanf("%d%d%d",&x,&y,&z);
DO1(x,y,z);
}
if(s=="Change"){
scanf("%d%d",&x,&z);
if(dep[edge[x*2-1].to]<dep[edge[x*2].to]) x=edge[x*2].to;
else x=edge[x*2-1].to;
change2(1,1,n,in[x],in[x],z);
}
if(s=="Cover"){
scanf("%d%d%d",&x,&y,&z);
DO2(x,y,z);
}
}
return 0;
}小结
这一题不难，就是一道树剖模板。