月下“毛景树”

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题目

click it!!
更好or更差的体验

思路

看完题目之后，很明显这是一道树剖题。为什么这么说呢？

  1. 他会改变树上两点的路径上的边权。
  2. 他要查询树上两点的路径上的最大边。
  3. 他要改变某条边的边权

从这几点来看就是说我们要在树上做区间操作！！！

这里有好多难点：

  1. 边权是很难使用的，不如将其改为点权
  2. 如何用树剖出的几条链组成的序列来进行各种操作

这里我们用线段树来进行区间操作，将边权改为“这条边的一个端点到另一个端点的所花费的值”（两个端点为父子节点的关系），这样就可以将边权化为点权。

比如：$u \to v$这条边的值为3，我们可以将它变为p[v]=3;(意思是v到u这条边的边权为3)。

代码

假设树剖之后我们用in[x]表示x这个点的dfs序，id[x]表示x这个编号对应的点（本人英语不好，数组名瞎取的）

之后我就直接给出线段树的操作代码:(别说你连线段树都不懂就来学树剖)

建树

1
2
3
4
5
6
7
8
9
10
11
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）)

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
}

区间加操作

1
2
3
4
5
6
7
8
9
10
11
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]);
}//简单易懂，线段树基本操作

区间覆盖

1
2
3
4
5
6
7
8
9
10
11
12
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]);
}//不说了...

区间查询最值

1
2
3
4
5
6
7
8
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;
}

树上查询

（这是在树上查询，树剖的大作用就是这个，会详解）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}

还有两个树上修改

大家结合上面的修改看看吧（这不是我偷懒！！）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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呢，因为之前有写过了

这是链接

谢谢大家的阅读！！！！！！！！！！！！！！！！！！！！！

下面给出完整代码：

完整代码

（码风就不要在意了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#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;
}

小结

这一题不难，就是一道树剖模板。