NC210168. 月下“毛景树”
描述
输入描述
第一行一个正整数N。 接下来N-1行,每行三个正整数Ui,Vi和Wi,第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi,树枝上有Wi个毛毛果。 接下来是操作和询问,以“Stop”结束。
输出描述
对于毛毛虫的每个询问操作,输出一个答案。
示例1
输入:
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
输出:
9 16
C++(clang++ 11.0.1) 解法, 执行用时: 410ms, 内存消耗: 20504K, 提交时间: 2023-03-20 21:22:44
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+7; struct E{ int v,w,nxt; }e[N]; int head[N],cnt=1; inline void addedge(int u,int v,int w){ e[++cnt]=(E){v,w,head[u]};head[u]=cnt; } int sz[N],dep[N],son[N],fa[N],val[N],eid[N]; int idx=0,dfn[N],idfn[N],bel[N]; void dfs1(int x,int f){ dep[x]=dep[f]+1; fa[x]=f;sz[x]=1; for(int i=head[x];i;i=e[i].nxt){ int to=e[i].v; if(to==f) continue; val[to]=e[i].w; eid[i/2]=to; dfs1(to,x); sz[x]+=sz[to]; if(sz[to]>sz[son[x]]) son[x]=to; } } void dfs2(int x,int tp){ bel[x]=tp; dfn[x]=++idx;idfn[idx]=x; if(son[x]) dfs2(son[x],tp); for(int i=head[x];i;i=e[i].nxt){ int to=e[i].v; if(to==fa[x]||to==son[x]) continue; dfs2(to,to); } } int mx[N<<2],add[N<<2],cov[N<<2]; #define ls (p<<1) #define rs (p<<1|1) #define mid ((l+r)>>1) void pushdown(int p,int l,int r){ if(cov[p]!=-1){ mx[ls]=mx[rs]=cov[p]; cov[ls]=cov[rs]=cov[p]; add[ls]=add[rs]=0; cov[p]=-1; } if(add[p]){ mx[ls]+=add[p];mx[rs]+=add[p]; add[ls]+=add[p];add[rs]+=add[p]; add[p]=0; } } void build(int p,int l,int r){ cov[p]=-1;add[p]=0; if(l==r){ mx[p]=val[idfn[l]]; return; } build(ls,l,mid); build(rs,mid+1,r); mx[p]=max(mx[ls],mx[rs]); } void modify(int p,int l,int r,int ql,int qr,int w){ if(ql>qr) return; if(ql<=l&&r<=qr){ mx[p]=cov[p]=w; add[p]=0; return; } pushdown(p,l,r); if(ql<=mid) modify(ls,l,mid,ql,qr,w); if(qr>mid) modify(rs,mid+1,r,ql,qr,w); mx[p]=max(mx[ls],mx[rs]); } void update(int p,int l,int r,int ql,int qr,int w){ if(ql>qr) return; if(ql<=l&&r<=qr){ mx[p]+=w;add[p]+=w; return; } pushdown(p,l,r); if(ql<=mid) update(ls,l,mid,ql,qr,w); if(qr>mid) update(rs,mid+1,r,ql,qr,w); mx[p]=max(mx[ls],mx[rs]); } int query(int p,int l,int r,int ql,int qr){ if(ql>qr) return 0; if(ql<=l&&r<=qr) return mx[p]; pushdown(p,l,r); int res=0; if(ql<=mid) res=query(ls,l,mid,ql,qr); if(qr>mid) res=max(res,query(rs,mid+1,r,ql,qr)); return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n;string str; cin>>n; for(int i=1,u,v,w;i<n;++i){ cin>>u>>v>>w; addedge(u,v,w); addedge(v,u,w); } val[1]=0;dep[1]=1; dfs1(1,0); dfs2(1,1); //树链剖分 build(1,1,n); // for(int i=1;i<=n;++i) cout<<i<<" "<<val[i]<<" "<<dfn[i]<<" "<<idfn[i]<<" "<<" ~~\n"; int k,u,v,w; cin>>str; while(str!="Stop"){ if(str=="Change"){ cin>>k>>w; int to=eid[k]; modify(1,1,n,dfn[to],dfn[to],w); }else if(str=="Cover"){ cin>>u>>v>>w; while(bel[u]^bel[v]){ if(dep[bel[u]]<dep[bel[v]]) swap(u,v); modify(1,1,n,dfn[bel[u]],dfn[u],w); u=fa[bel[u]]; } if(dep[u]<dep[v]) swap(u,v); modify(1,1,n,dfn[v]+1,dfn[u],w); }else if(str=="Add"){ cin>>u>>v>>w; while(bel[u]^bel[v]){ if(dep[bel[u]]<dep[bel[v]]) swap(u,v); update(1,1,n,dfn[bel[u]],dfn[u],w); u=fa[bel[u]]; } if(dep[u]<dep[v]) swap(u,v); update(1,1,n,dfn[v]+1,dfn[u],w); }else if(str=="Max"){ cin>>u>>v; int ans=0; while(bel[u]^bel[v]){ if(dep[bel[u]]<dep[bel[v]]) swap(u,v); // cout<<" "<<bel[u]<<" "<<u<<" "<<idfn[bel[u]]<<" "<<idfn[u]<<" "<<query(1,1,n,dfn[bel[u]],dfn[u])<<"!!\n"; ans=max(ans,query(1,1,n,dfn[bel[u]],dfn[u])); u=fa[bel[u]]; } if(dep[u]<dep[v]) swap(u,v); ans=max(ans,query(1,1,n,dfn[v]+1,dfn[u])); cout<<ans<<"\n"; } cin>>str; } return 0; }