P4315 【月下“毛景树”】

一道~~毒瘤~~树链剖分 主要思想就是把边权化为点权 与P1505 旅游有些类似 先进行dfs,之后枚举编号为奇数的边 使奇数边的to比from的深度大 然后把边权存为to的点权即可 维护一个区间加法标记和一个区间覆盖标记 接下来就是普通线段树操作了 ~~我才不会说我少打一个pushdown调了两个小时~~ 感谢@da32s1da 大佬的帮助！ 丑陋的代码： ```cpp #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; const int N=1e5+5; struct edge { int from,to,nxt,dis; }edge[N<<1]; int n,num,head[N],fa[N],son[N],tot[N],tag[N<<2]; int cnt,idx[N],top[N],dep[N],w[N],maxn[N<<2],lazy[N<<2]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to,int dis) { edge[++num].nxt=head[from]; edge[num].from=from; edge[num].to=to; edge[num].dis=dis; head[from]=num; } void dfs(int k,int father,int deep) { int bigson=0; fa[k]=father; dep[k]=deep; tot[k]=1; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v==father) continue; dfs(v,k,deep+1); tot[k]+=tot[v]; if (bigson<tot[v]) { bigson=tot[v]; son[k]=v; } } } void dfs(int k,int tp) { idx[k]=++cnt; top[k]=tp; if (!son[k]) return; dfs(son[k],tp); for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (!idx[v]) dfs(v,v); } } inline void pushup(int now) { maxn[now]=max(maxn[now<<1],maxn[now<<1|1]); } inline void pushdown(int now) { if (tag[now]!=-1) { maxn[now<<1]=maxn[now<<1|1]=tag[now]; tag[now<<1]=tag[now<<1|1]=tag[now]; lazy[now<<1]=lazy[now<<1|1]=0; tag[now]=-1; } if (lazy[now]) { lazy[now<<1]+=lazy[now]; lazy[now<<1|1]+=lazy[now]; maxn[now<<1]+=lazy[now]; maxn[now<<1|1]+=lazy[now]; lazy[now]=0; } } void build(int l,int r,int now) { lazy[now]=0; tag[now]=-1; if (l==r) { maxn[now]=w[l]; return; } int mid=(l+r)>>1; build(l,mid,now<<1); build(mid+1,r,now<<1|1); pushup(now); } void outchange(int p,int l,int r,int now,int c) { if (l==r) { maxn[now]=c; return; } int mid=(l+r)>>1; pushdown(now); if (p<=mid) outchange(p,l,mid,now<<1,c); else outchange(p,mid+1,r,now<<1|1,c); pushup(now); } void inchange(int L,int R,int l,int r,int now,int c)//都修改为一个数 { if (l>R||r<L) return; if (l>=L&&r<=R) { maxn[now]=c; tag[now]=c; lazy[now]=0; return; } int mid=(l+r)>>1; pushdown(now); if (mid>=R) inchange(L,R,l,mid,now<<1,c); else if (mid<L) inchange(L,R,mid+1,r,now<<1|1,c); else { inchange(L,mid,l,mid,now<<1,c); inchange(mid+1,R,mid+1,r,now<<1|1,c); } pushup(now); } void inchanges(int L,int R,int l,int r,int now,int c)//都加上一个数 { if (l>R||r<L) return; if (l>=L&&r<=R) { maxn[now]+=c; lazy[now]+=c; return; } int mid=(l+r)>>1; pushdown(now); if (mid>=R) inchanges(L,R,l,mid,now<<1,c); else if (mid<L) inchanges(L,R,mid+1,r,now<<1|1,c); else { inchanges(L,mid,l,mid,now<<1,c); inchanges(mid+1,R,mid+1,r,now<<1|1,c); } pushup(now); } int getmax(int L,int R,int l,int r,int now) { if (l>R||r<L) return -1e9; if (l>=L&&r<=R) return maxn[now]; int mid=(l+r)>>1; pushdown(now); if (mid>=R) return getmax(L,R,l,mid,now<<1); if (mid<L) return getmax(L,R,mid+1,r,now<<1|1); return max(getmax(L,mid,l,mid,now<<1),getmax(mid+1,R,mid+1,r,now<<1|1)); } inline void treechange(int x,int y,int val)//都修改为一个数 { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); inchange(idx[top[x]],idx[x],1,n,1,val); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); inchange(idx[x]+1,idx[y],1,n,1,val); } inline void treechanges(int x,int y,int val)//都加上一个数 { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); inchanges(idx[top[x]],idx[x],1,n,1,val); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); inchanges(idx[x]+1,idx[y],1,n,1,val); } inline int treemax(int x,int y) { int ans=-1e9; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans=max(ans,getmax(idx[top[x]],idx[x],1,n,1)); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); return max(ans,getmax(idx[x]+1,idx[y],1,n,1)); } int main() { n=read(); for (reg int i=1;i<n;i++) { int x=read(),y=read(),z=read(); add_edge(x,y,z); add_edge(y,x,z); } dfs(1,0,1); dfs(1,1); for (reg int i=1;i<=num;i+=2) { int &u=edge[i].from,&v=edge[i].to; if (dep[u]>dep[v]) swap(u,v); w[idx[v]]=edge[i].dis; } build(1,n,1); while (1) { char opt[10]; scanf("%s",opt); if (opt[0]=='S') break; int x=read(),y=read(); if (opt[0]=='C') if (opt[1]=='h') outchange(idx[edge[(x<<1)-1].to],1,n,1,y); else treechange(x,y,read()); if (opt[0]=='A') treechanges(x,y,read()); if (opt[0]=='M') printf("%d\n",treemax(x,y)); } return 0; } ```