题解 P4315 【月下“毛景树”】
温词
·
·
题解
在两天的调试后，我终于a了这道题，果然还是没有学会放下，不知道写的什么神仙push_down
首先先把边权转换成子节点的点权，这个在第一次dfs中就可以实现了，这道题要维护的几个操作大概如下：1、单点修改 2、区间覆盖 3、区间加 4、区间查询最大值。都没有什么亮点，常规操作吧。接下来就看代码把（5k代码警告）
#include<bits/stdc++.h>
#define int long long//好习惯，不开long long见祖宗
#define INF 0x3f3f3f3f
using namespace std;
inline int read(){
int w=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+ch-48;
ch=getchar();
}
return w*f;
} //咸鱼快读
int ans,n,m,R,Mod,cnt,head[1000010],depth[1000010],son[1000010],f[1000010],top[1000010],tot,id[1000010],a[1000010],val[1000010],size[1000010];
bool debug;
struct Edge{
int from,to,next,dis;
}edge[1000010];
inline void addedge(int u,int v,int w){
cnt++;
edge[cnt].from=u;
edge[cnt].to=v;
edge[cnt].dis=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
inline void dfs1(int u,int fa){
f[u]=fa;depth[u]=depth[fa]+1;
size[u]=1;int v,i,j,k;
int maxson=-1;
for(i=head[u];i;i=edge[i].next){
v=edge[i].to;if(v==fa) continue;
a[v]=edge[i].dis;//边权转换成点权
dfs1(v,u);size[u]+=size[v];
if(size[v]>maxson){
maxson=size[v];son[u]=v;
}
}
return;
}
inline void dfs2(int u,int top_fa){
tot++;id[u]=tot;top[u]=top_fa;
val[tot]=a[u];int i,j,k,v;
if(!son[u]) return;
dfs2(son[u],top_fa);
for(i=head[u];i;i=edge[i].next){
v=edge[i].to;if(id[v]) continue;
dfs2(v,v);
}
return;
}//都是常规操作，毫无亮点
struct Node{
int l,r,maxx,cov_tag,add_tag;
}st[1000010];//线段树部分
inline int ls(int p){
return p<<1;
}//左儿子
inline int rs(int p){
return p<<1|1;
}//右儿子
inline void push_up(int p){
st[p].maxx=max(st[ls(p)].maxx,st[rs(p)].maxx);return;
}//上推，只要上推一个最大值就行，并不麻烦
inline void build(int p,int l,int r){
st[p].l=l;st[p].r=r;st[p].cov_tag=-1;st[p].add_tag=0;
if(l==r){
st[p].maxx=val[l];return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);build(rs(p),mid+1,r);push_up(p);return;
}//常规建树，毫无亮点
inline void push_down(int p){
if(st[p].cov_tag!=-1){
st[ls(p)].cov_tag=st[rs(p)].cov_tag=st[p].cov_tag;//下移覆盖标记
st[ls(p)].maxx=st[rs(p)].maxx=st[p].cov_tag;//因为覆盖所以当前区间的最大值也被覆盖了
st[ls(p)].add_tag=st[rs(p)].add_tag=0;//清空子节点的加标记
}//此处注意，先进行覆盖标记下推，再进行区间加标记下移
st[ls(p)].add_tag+=st[p].add_tag;//哦我一开始以为下移覆盖就不用下移区间加，WA成傻子
st[rs(p)].add_tag+=st[p].add_tag;
st[ls(p)].maxx+=st[p].add_tag;
st[rs(p)].maxx+=st[p].add_tag;
st[p].add_tag=0;st[p].cov_tag=-1;return;//记得清空
}
inline void interval_add(int p,int l,int r,int val){
if(st[p].l>=l&&st[p].r<=r){
st[p].maxx+=val;
st[p].add_tag+=val;return;
}
push_down(p);
int mid=(st[p].l+st[p].r)>>1;
if(l<=mid) interval_add(ls(p),l,r,val);
if(r>mid) interval_add(rs(p),l,r,val);
push_up(p);return;
}//常规区间加
inline void interval_cover(int p,int l,int r,int val){
if(st[p].l>=l&&st[p].r<=r){
st[p].add_tag=0;st[p].cov_tag=val;
st[p].maxx=val;return;
}
push_down(p);
int mid=(st[p].l+st[p].r)>>1;
if(l<=mid) interval_cover(ls(p),l,r,val);
if(r>mid) interval_cover(rs(p),l,r,val);
push_up(p);return;
}//常规区间覆盖
inline void tree_cover(int x,int y,int z){
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]]) swap(x,y);
interval_cover(1,id[top[x]],id[x],z);
x=f[top[x]];
}
if(depth[x]>depth[y]) swap(x,y);
interval_cover(1,id[x]+1,id[y],z);return;
}//常规跳链
inline void tree_add(int x,int y,int z){
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]]) swap(x,y);
interval_add(1,id[top[x]],id[x],z);
x=f[top[x]];
}
if(depth[x]>depth[y]) swap(x,y);
interval_add(1,id[x]+1,id[y],z);return;
}//常规跳链
inline int interval_query(int p,int l,int r){
if(st[p].l>=l&&st[p].r<=r){
return st[p].maxx;
}
push_down(p);
int mid=(st[p].l+st[p].r)>>1;int sum=-INF;
if(l<=mid) sum=max(sum,interval_query(ls(p),l,r));
if(r>mid) sum=max(sum,interval_query(rs(p),l,r));
return sum;
}//常规区间最大值
inline int tree_query(int x,int y){
int sum=-INF;
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]]) swap(x,y);
sum=max(sum,interval_query(1,id[top[x]],id[x]));
x=f[top[x]];
}
if(depth[x]>depth[y]) swap(x,y);
sum=max(sum,interval_query(1,id[x]+1,id[y]));return sum;
}//常规跳链
signed main(){
n=read();int i,j,k;
for(i=1;i<n;i++){
int x,y,z;
x=read();y=read();z=read();
addedge(x,y,z);addedge(y,x,z);
}
dfs1(1,0);dfs2(1,1);build(1,1,n);
//debug=true;
while(true){
string s;cin>>s;int x,y,z;
if(s[1]=='t') break;
if(s[1]=='h'){//change
x=read();y=read();
int u=edge[x*2].from,v=edge[x*2].to;
if(depth[u]>depth[v]){//单点修改注意两个地方，首先因为深度更大的是儿子，所以修改深度大的，其次修改的是id[]
interval_cover(1,id[u],id[u],y);
}
else{
interval_cover(1,id[v],id[v],y);
}
}
if(s[1]=='o'){//cover
x=read();y=read();z=read();
tree_cover(x,y,z);
}
if(s[1]=='d'){//add
x=read();y=read();z=read();
tree_add(x,y,z);
}
if(s[1]=='a'){//max
x=read();y=read();ans=tree_query(x,y);
printf("%d\n",ans);
}//常规操作稳住
}
return 0;
}
嗯整份代码大概就是这样，思路不难，反正我是到处写挂，菜是原罪希望大家一遍轻松AC