P4315 月下“毛景树” 题解

àì夳堔傛蜴生んèń 2023-06-01 15:53 23阅读 0赞

### P4315 月下“毛景树” 题解 ###

[题目链接][Link 1]

这道题目是比较裸的树剖+线段树题目，只不过有一些细节需要注意。

首先，这道题目是边权，所以我们要转成点权，因为每一条边都对应它下面的一个点，所以我们用它下面点的权值来代替边权。

然后在线段树处理链顶边界的时候，左区间要+1

\\(like this\\)

query(1,1,n,l+1,r);

原理：处理链顶时是在重链上，根据`dfs_2`的遍历顺序，所以当前区间+1肯定就是重儿子

但是这样就会出现一个问题，看下面这种情况

![mRvVsI.png][]

很明显查询1-2这条链的时候，最后都跳到了1，如果左区间再加1的线段树就会无限递归，所以这里也要特判一下。

if (l+1>r) return maxx; else return max(maxx,query(1,1,n,l+1,r));

关于线段树标记的下传

有两种下传方法：

1.  先下传加，再下传覆盖  
    这样下传就不能分清当前覆盖究竟是在加之前还是之后
2.  先下传覆盖，同时将儿子的加清零，这样就不会有上面的烦恼，`update`要在打覆盖标记的时候把加标记清零

t[ls].add=t[rs].add=0;

代码

// luogu-judger-enable-o2 #include<iostream> #include<cstdio> #define pii pair<int,int> #define mp make_pair #define one first #define two second using namespace std; const int N=1e5+100; struct Tree{ int ls,rs,maxx,add,fix; }t[N<<1]; struct edge{ int s,e,v,net; }ed[N<<1]; int n,tot,idx,cnt=1; int head[N],w[N],father[N],son[N],size[N],top[N],deep[N],id[N],fv[N]; pii p[N]; inline void push_up(int rt) { t[rt].maxx=max(t[t[rt].ls].maxx,t[t[rt].rs].maxx); return ; } inline void push_down(int rt,int l,int r) { int ls=t[rt].ls,rs=t[rt].rs; if (t[rt].fix!=-1) { int k=t[rt].fix; t[ls].fix=k; t[ls].maxx=k; t[rs].fix=k; t[rs].maxx=k; t[rt].fix=-1; t[ls].add=t[rs].add=0; } if (t[rt].add) { int k=t[rt].add; t[ls].add+=k; t[ls].maxx+=k; t[rs].add+=k; t[rs].maxx+=k; t[rt].add=0; } return ; } inline int query(int rt,int l,int r,int nl,int nr) { if (l==nl&&r==nr) return t[rt].maxx; int mid=(l+r)>>1; push_down(rt,l,r); if (nr<=mid) return query(t[rt].ls,l,mid,nl,nr); else if (nl>mid) return query(t[rt].rs,mid+1,r,nl,nr); else return max(query(t[rt].ls,l,mid,nl,mid),query(t[rt].rs,mid+1,r,mid+1,nr)); } inline void update(int rt,int l,int r,int nl,int nr,int opt,int k) { if (l==nl&&r==nr) { if (opt==1) { t[rt].add+=k; t[rt].maxx+=k; } if (opt==2) { t[rt].fix=k; t[rt].maxx=k; t[rt].add=0; } return ; } int mid=(l+r)>>1; push_down(rt,l,r); if (nr<=mid) update(t[rt].ls,l,mid,nl,nr,opt,k); else if (nl>mid) update(t[rt].rs,mid+1,r,nl,nr,opt,k); else { update(t[rt].ls,l,mid,nl,mid,opt,k); update(t[rt].rs,mid+1,r,mid+1,nr,opt,k); } push_up(rt); return ; } inline void update_link(int x,int y,int opt,int k) { while (top[x]!=top[y]) { if (deep[top[x]]>deep[top[y]]) swap(x,y); update(1,1,n,id[top[y]],id[y],opt,k); y=father[top[y]]; } int l=id[x],r=id[y]; if (l>r) swap(l,r); if (l+1>r) return ; update(1,1,n,l+1,r,opt,k); return ; } inline int query_link(int x,int y) { int maxx=0; while (top[x]!=top[y]) { if (deep[top[x]]>deep[top[y]]) swap(x,y); maxx=max(query(1,1,n,id[top[y]],id[y]),maxx); y=father[top[y]]; } int l=id[x],r=id[y]; if (l>r) swap(l,r); if (l+1>r) return maxx; else return max(maxx,query(1,1,n,l+1,r)); } inline void dfs_2(int x,int tp) { id[x]=++idx; w[idx]=fv[x]; top[x]=tp; if (son[x]) dfs_2(son[x],tp); for (int i=head[x];i;i=ed[i].net) if (ed[i].e!=father[x]&&ed[i].e!=son[x]) dfs_2(ed[i].e,ed[i].e); return ; } inline void dfs_1(int x,int fa) { deep[x]=deep[fa]+1; father[x]=fa; size[x]=1; for (int i=head[x];i;i=ed[i].net) if (ed[i].e!=fa) { dfs_1(ed[i].e,x); size[x]+=size[ed[i].e]; if (size[son[x]]<size[ed[i].e]) son[x]=ed[i].e; } else fv[x]=ed[i].v; return ; } inline void build(int rt,int l,int r) { t[rt].fix=-1; t[rt].add=0; if (l==r) { t[rt].maxx=w[l]; return ; } int mid=(l+r)>>1; t[rt].ls=++cnt; build(t[rt].ls,l,mid); t[rt].rs=++cnt; build(t[rt].rs,mid+1,r); push_up(rt); return ; } inline void add(int s,int e,int v) { ed[++tot]=(edge){s,e,v,head[s]}; head[s]=tot; return ; } int main() { scanf("%d",&n); for (int i=1;i<=n-1;i++) { int s,e,v; scanf("%d%d%d",&s,&e,&v); p[i]=mp(s,e); add(s,e,v);add(e,s,v); } dfs_1(1,0); dfs_2(1,1); build(1,1,n); while (1) { char ss[15]; int u,v,w,k; scanf("%s",ss+1); if (ss[1]=='S') return 0; if (ss[2]=='h') { scanf("%d%d",&k,&w); int x=p[k].one,y=p[k].two; if (deep[x]>deep[y]) swap(x,y); update(1,1,n,id[y],id[y],2,w); } if (ss[2]=='o') { scanf("%d%d%d",&u,&v,&w); update_link(u,v,2,w); } if (ss[1]=='A') { scanf("%d%d%d",&u,&v,&w); update_link(u,v,1,w); } if (ss[1]=='M') { scanf("%d%d",&u,&v); printf("%d\n",query_link(u,v)); } } return 0; }

收获:线段树在下传标记的时候一定要考虑怎样下传才不会相互影响，或者直接打时间戳

转载于:https://www.cnblogs.com/last-diary/p/11411563.html

[Link 1]: https://www.luogu.org/problem/P4315
[mRvVsI.png]: /images/20230601/f512842222a245d6991e497fc3d01f32.png