BZOJ 1984: 月下“毛景树”

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题解
代码

Description

毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有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之间树枝上毛毛果个数最多有多少个。

Input

第一行一个正整数N。接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。接下来是操作和询问，以“Stop”结束。

Output

对于毛毛虫的每个询问操作，输出一个答案。

Sample Input

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

Sample Output

9
16【Data Range】
1<=N<=100,000，操作+询问数目不超过100,000。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。

题解

这道题目还是树链剖分+线段树，熟练剖分还是老样子，线段树的话维护一个coverTag和addTag就可以过了。
【P.s. 写这题的时候不小心打错了两个变量名，结果又T又W真是、、、QAQ

代码

/*Author:WNJXYK*/
#include<cstdio>
using namespace std;
const int Maxn=100000;
int siz[Maxn+5],dep[Maxn+5],son[Maxn+5],fa[Maxn+5],w[Maxn+5],top[Maxn+5];
int totw=0;
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int a,int b){
        v=a;nxt=b;
    }
};
Edge e[Maxn*2+5];
int nume=0;
int head[Maxn+5];
struct Input{
    int x,y,w;
    Input(){}
    Input(int a,int b,int c){
        x=a;y=b;w=c;
    }
};
Input ipt[Maxn+5];
struct Btree{
    int left,right;
    int max;
    int addTag,coverTag;
};
Btree tree[8*Maxn+5];
inline int remax(int a,int b){
    if (a>b) return a;
    return b;
}
inline void addEdge(int x,int y){
    e[++nume]=Edge(x,head[y]);
    head[y]=nume;
    e[++nume]=Edge(y,head[x]);
    head[x]=nume;
}
void _build(int x,int left,int right){
    tree[x].left=left;tree[x].right=right;
    tree[x].max=tree[x].addTag=0;tree[x].coverTag=-1;
    if (tree[x].left==tree[x].right){
        //Nothing to do
    }else{
        int mid=(left+right)/2;
        _build(x*2,left,mid);
        _build(x*2+1,mid+1,right);
    }
}
void _update(int x){
    if (tree[x].left==tree[x].right) return ;
    tree[x].max=remax(tree[x*2].max,tree[x*2+1].max);
}
void _clean(int x){
    if (tree[x].left==tree[x].right) return;
    if (tree[x].coverTag!=-1){
        tree[x*2].addTag=tree[x*2+1].addTag=0;
        tree[x*2].coverTag=tree[x*2+1].coverTag=tree[x].coverTag;
        tree[x*2].max=tree[x*2+1].max=tree[x].coverTag;
        tree[x].coverTag=-1;
    }
    if (tree[x].addTag!=0){
        tree[x*2].max+=tree[x].addTag;
        tree[x*2+1].max+=tree[x].addTag;
        if (tree[x*2].coverTag!=-1)
            tree[x*2].coverTag+=tree[x].addTag;
        else
            tree[x*2].addTag+=tree[x].addTag;
        if (tree[x*2+1].coverTag!=-1)
            tree[x*2+1].coverTag+=tree[x].addTag;
        else
            tree[x*2+1].addTag+=tree[x].addTag;
        tree[x].addTag=0;
    }
}
void _add(int x,int left,int right,int val){
    _clean(x);
    if (left<=tree[x].left && tree[x].right<=right){
        tree[x].max+=val;tree[x].addTag=val;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        if (left<=mid) _add(x*2,left,right,val);
        if (right>mid) _add(x*2+1,left,right,val);
        _update(x);
    }
}
void _cover(int x,int left,int right,int val){
    _clean(x);
    if (left<=tree[x].left && tree[x].right<=right){
        tree[x].max=val;tree[x].coverTag=val;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        if (left<=mid) _cover(x*2,left,right,val);
        if (right>mid) _cover(x*2+1,left,right,val);
        _update(x);
    }
}
int _query(int x,int left,int right){
    _clean(x);
    if (left<=tree[x].left && tree[x].right<=right){
        return tree[x].max;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        int res=0;
        if (left<=mid) res=remax(res,_query(x*2,left,right));
        if (right>mid) res=remax(res,_query(x*2+1,left,right));
        return res;
    }
}
void dfs_1(int x){
    siz[x]=1;son[x]=0;
    for (int i=head[x];i;i=e[i].nxt){
        if (e[i].v!=fa[x]){
            fa[e[i].v]=x;
            dep[e[i].v]=dep[x]+1;
            dfs_1(e[i].v);
            if (siz[e[i].v]>siz[son[x]]) son[x]=e[i].v;
            siz[x]+=siz[e[i].v];
        }
    }
}
void dfs_2(int x,int tp){
    w[x]=++totw;top[x]=tp;
    if (son[x]!=0) dfs_2(son[x],tp);
    for (int i=head[x];i;i=e[i].nxt){
        if (e[i].v!=fa[x] && e[i].v!=son[x]){
            dfs_2(e[i].v,e[i].v);
        }
    }
}
inline void swap(int &a,int &b){
    int tmp=a;
    a=b;
    b=tmp;
}
inline int query(int u,int v){
    int f1=top[u],f2=top[v];
    int res=0;
    while(f1!=f2){
        if (dep[f1]<dep[f2]){
            swap(f1,f2);
            swap(u,v);
        }
        res=remax(res,_query(1,w[f1],w[u]));
        u=fa[f1];f1=top[u];
    }
    if (u==v) return res;
    if (dep[u]>dep[v]) swap(u,v);
    return remax(res,_query(1,w[son[u]],w[v]));
}
inline void cover(int u,int v,int val){
    int f1=top[u],f2=top[v];
    while(f1!=f2){
        if (dep[f1]<dep[f2]){
            swap(f1,f2);
            swap(u,v);
        }
        _cover(1,w[f1],w[u],val);
        u=fa[f1];f1=top[u];
    }
    if (u==v) return ;
    if (dep[u]>dep[v]) swap(u,v);
    _cover(1,w[son[u]],w[v],val);
}
inline void add(int u,int v,int val){
    int f1=top[u],f2=top[v];
    while(f1!=f2){
        if (dep[f1]<dep[f2]){
            swap(f1,f2);
            swap(u,v);
        }
        _add(1,w[f1],w[u],val);
        u=fa[f1];f1=top[u];
    }
    if (u==v) return ;
    if (dep[u]>dep[v]) swap(u,v);
    _add(1,w[son[u]],w[v],val);
}
int n;
int main(){
    scanf("%d",&n);
    _build(1,1,n);
    for (int i=1;i<n;i++){
        scanf("%d%d%d",&ipt[i].x,&ipt[i].y,&ipt[i].w);
        addEdge(ipt[i].x,ipt[i].y);
    }
    fa[1]=1;dep[1]=1;
    dfs_1(1);
    dfs_2(1,1);
    for (int i=1;i<n;i++){
        if (dep[ipt[i].x]<dep[ipt[i].y]) swap(ipt[i].x,ipt[i].y);
        _cover(1,w[ipt[i].x],w[ipt[i].x],ipt[i].w);
    }
    char ch[10];
    int x,y,z;
    scanf("%s",&ch);
    while(ch[1]!='t'){
        if (ch[1]=='a'){
            scanf("%d%d",&x,&y);
            printf("%dn",query(x,y));
        }
        if (ch[1]=='o'){
            scanf("%d%d%d",&x,&y,&z);
            cover(x,y,z);
        }
        if (ch[1]=='d'){
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
        }
        if (ch[1]=='h'){
            scanf("%d%d",&x,&y);
            _cover(1,w[ipt[x].x],w[ipt[x].x],y);
        }
        scanf("%s",&ch);
    }
    return 0;
}

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

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

/*Author:WNJXYK*/

#include<cstdio>

using namespace std;

const int Maxn=100000;

int siz[Maxn+5],dep[Maxn+5],son[Maxn+5],fa[Maxn+5],w[Maxn+5],top[Maxn+5];

int totw=0;

struct Edge{

int v,nxt;

Edge(){}

Edge(int a,int b){

v=a;nxt=b;

}

};

Edge e[Maxn*2+5];

int nume=0;

int head[Maxn+5];

struct Input{

int x,y,w;

Input(){}

Input(int a,int b,int c){

x=a;y=b;w=c;

}

};

Input ipt[Maxn+5];

struct Btree{

int left,right;

int max;

int addTag,coverTag;

};

Btree tree[8*Maxn+5];

inline int remax(int a,int b){

if (a>b) return a;

return b;

}

inline void addEdge(int x,int y){

e[++nume]=Edge(x,head[y]);

head[y]=nume;

e[++nume]=Edge(y,head[x]);

head[x]=nume;

}

void _build(int x,int left,int right){

tree[x].left=left;tree[x].right=right;

tree[x].max=tree[x].addTag=0;tree[x].coverTag=-1;

if (tree[x].left==tree[x].right){

//Nothing to do

}else{

int mid=(left+right)/2;

_build(x*2,left,mid);

_build(x*2+1,mid+1,right);

}

void _update(int x){

if (tree[x].left==tree[x].right) return ;

tree[x].max=remax(tree[x*2].max,tree[x*2+1].max);

}

void _clean(int x){

if (tree[x].left==tree[x].right) return;

if (tree[x].coverTag!=-1){

tree[x*2].addTag=tree[x*2+1].addTag=0;

tree[x*2].coverTag=tree[x*2+1].coverTag=tree[x].coverTag;

tree[x*2].max=tree[x*2+1].max=tree[x].coverTag;

tree[x].coverTag=-1;

}

if (tree[x].addTag!=0){

tree[x*2].max+=tree[x].addTag;

tree[x*2+1].max+=tree[x].addTag;

if (tree[x*2].coverTag!=-1)

tree[x*2].coverTag+=tree[x].addTag;

else

tree[x*2].addTag+=tree[x].addTag;

if (tree[x*2+1].coverTag!=-1)

tree[x*2+1].coverTag+=tree[x].addTag;

else

tree[x*2+1].addTag+=tree[x].addTag;

tree[x].addTag=0;

}

void _add(int x,int left,int right,int val){

_clean(x);

if (left<=tree[x].left && tree[x].right<=right){

tree[x].max+=val;tree[x].addTag=val;

}else{

int mid=(tree[x].left+tree[x].right)/2;

if (left<=mid) _add(x*2,left,right,val);

if (right>mid) _add(x*2+1,left,right,val);

_update(x);

}

void _cover(int x,int left,int right,int val){

_clean(x);

if (left<=tree[x].left && tree[x].right<=right){

tree[x].max=val;tree[x].coverTag=val;

}else{

int mid=(tree[x].left+tree[x].right)/2;

if (left<=mid) _cover(x*2,left,right,val);

if (right>mid) _cover(x*2+1,left,right,val);

_update(x);

}

int _query(int x,int left,int right){

_clean(x);

if (left<=tree[x].left && tree[x].right<=right){

return tree[x].max;

}else{

int mid=(tree[x].left+tree[x].right)/2;

int res=0;

if (left<=mid) res=remax(res,_query(x*2,left,right));

if (right>mid) res=remax(res,_query(x*2+1,left,right));

return res;

}

void dfs_1(int x){

siz[x]=1;son[x]=0;

for (int i=head[x];i;i=e[i].nxt){

if (e[i].v!=fa[x]){

fa[e[i].v]=x;

dep[e[i].v]=dep[x]+1;

dfs_1(e[i].v);

if (siz[e[i].v]>siz[son[x]]) son[x]=e[i].v;

siz[x]+=siz[e[i].v];

}

void dfs_2(int x,int tp){

w[x]=++totw;top[x]=tp;

if (son[x]!=0) dfs_2(son[x],tp);

for (int i=head[x];i;i=e[i].nxt){

if (e[i].v!=fa[x] && e[i].v!=son[x]){

dfs_2(e[i].v,e[i].v);

}

inline void swap(int &a,int &b){

int tmp=a;

a=b;

b=tmp;

}

inline int query(int u,int v){

int f1=top[u],f2=top[v];

int res=0;

while(f1!=f2){

if (dep[f1]<dep[f2]){

swap(f1,f2);

swap(u,v);

}

res=remax(res,_query(1,w[f1],w[u]));

u=fa[f1];f1=top[u];

}

if (u==v) return res;

if (dep[u]>dep[v]) swap(u,v);

return remax(res,_query(1,w[son[u]],w[v]));

}

inline void cover(int u,int v,int val){

int f1=top[u],f2=top[v];

while(f1!=f2){

if (dep[f1]<dep[f2]){

swap(f1,f2);

swap(u,v);

}

_cover(1,w[f1],w[u],val);

u=fa[f1];f1=top[u];

}

if (u==v) return ;

if (dep[u]>dep[v]) swap(u,v);

_cover(1,w[son[u]],w[v],val);

}

inline void add(int u,int v,int val){

int f1=top[u],f2=top[v];

while(f1!=f2){

if (dep[f1]<dep[f2]){

swap(f1,f2);

swap(u,v);

}

_add(1,w[f1],w[u],val);

u=fa[f1];f1=top[u];

}

if (u==v) return ;

if (dep[u]>dep[v]) swap(u,v);

_add(1,w[son[u]],w[v],val);

}

int n;

int main(){

scanf("%d",&n);

_build(1,1,n);

for (int i=1;i<n;i++){

scanf("%d%d%d",&ipt[i].x,&ipt[i].y,&ipt[i].w);

addEdge(ipt[i].x,ipt[i].y);

}

fa[1]=1;dep[1]=1;

dfs_1(1);

dfs_2(1,1);

for (int i=1;i<n;i++){

if (dep[ipt[i].x]<dep[ipt[i].y]) swap(ipt[i].x,ipt[i].y);

_cover(1,w[ipt[i].x],w[ipt[i].x],ipt[i].w);

}

char ch[10];

int x,y,z;

scanf("%s",&ch);

while(ch[1]!='t'){

if (ch[1]=='a'){

scanf("%d%d",&x,&y);

printf("%dn",query(x,y));

}

if (ch[1]=='o'){

scanf("%d%d%d",&x,&y,&z);

cover(x,y,z);

}

if (ch[1]=='d'){

scanf("%d%d%d",&x,&y,&z);

add(x,y,z);

}

if (ch[1]=='h'){

scanf("%d%d",&x,&y);

_cover(1,w[ipt[x].x],w[ipt[x].x],y);

}

scanf("%s",&ch);

}

return 0;

}

WNJXYKの博客

喂你脚下有坑