这是一道毒瘤题。
首先题目中给的是边权而不是点权，但是我们把边权移到点上就行了
但是要注意，之后我们修改u,v两点之间的路径时，就不要修改他们的lca，以及当要修改单边的时候，把边的编号*2(因为是双向边)，然后挑深度大的那个点来修改
重点是区间覆盖tag和区间加tag。首先注意，进行区间覆盖时，一定要清零区间加tag。然后其次，pushdown的时候一定要先覆盖再加
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define N 100005 using namespace std; template<class T> inline void read(T &x) { x=0; static char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int n,first[2*N],tot; struct Edge{int from,to,next,val;}edge[2*N]; inline void addedge(int x,int y,int z) { tot++; edge[tot].from=x; edge[tot].to=y; edge[tot].next=first[x]; edge[tot].val=z; first[x]=tot; } //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int depth[N],size[N],maxson[N],father[N],val[N]; void dfs1(int now,int fa) { depth[now]=depth[fa]+1; father[now]=fa; size[now]=1; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; dfs1(vis,now); val[vis]=edge[u].val; size[now]+=size[vis]; if(size[vis]>size[maxson[now]]) maxson[now]=vis; } } int top[N],id[N],wnew[N],sign; void dfs2(int now,int topf) { top[now]=topf; id[now]=++sign; wnew[sign]=val[now]; if(maxson[now]) dfs2(maxson[now],topf); for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==maxson[now]||vis==father[now]) continue; dfs2(vis,vis); } } //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ struct Tree{int l,r,maxv,cover,lazy_add;}tree[4*N]; inline void pushup(int now){ tree[now].maxv=max(tree[2*now].maxv,tree[2*now+1].maxv); } inline void pushdown(int now) { if(tree[now].cover!=-1) { tree[2*now].lazy_add=tree[2*now+1].lazy_add=0; tree[2*now].cover=tree[2*now].maxv=tree[now].cover; tree[2*now+1].cover=tree[2*now+1].maxv=tree[now].cover; tree[now].cover=-1; } tree[2*now].maxv+=tree[now].lazy_add; tree[2*now+1].maxv+=tree[now].lazy_add; tree[2*now].lazy_add+=tree[now].lazy_add; tree[2*now+1].lazy_add+=tree[now].lazy_add; tree[now].lazy_add=0; } void build(int now,int l,int r) { tree[now].l=l,tree[now].r=r,tree[now].cover=-1,tree[now].lazy_add=0; if(l==r) { tree[now].maxv=wnew[l]; return; } int m=(l+r)>>1; build(2*now,l,m); build(2*now+1,m+1,r); pushup(now); } inline void add(int now,int l,int r,int w) { if(l<=tree[now].l&&tree[now].r<=r) { tree[now].lazy_add+=w; tree[now].maxv+=w; return; } pushdown(now); int m=(tree[now].l+tree[now].r)>>1; if(l<=m) add(2*now,l,r,w); if(r>m) add(2*now+1,l,r,w); pushup(now); } inline void cover(int now,int l,int r,int w) { if(l<=tree[now].l&&tree[now].r<=r) { tree[now].cover=w; tree[now].maxv=w; tree[now].lazy_add=0; return; } pushdown(now); int m=(tree[now].l+tree[now].r)>>1; if(l<=m) cover(2*now,l,r,w); if(r>m) cover(2*now+1,l,r,w); pushup(now); } inline int query(int now,int l,int r) { if(l<=tree[now].l&&tree[now].r<=r) return tree[now].maxv; pushdown(now); int m=(tree[now].l+tree[now].r)>>1,res=-INF; if(l<=m) res=max(res,query(2*now,l,r)); if(r>m) res=max(res,query(2*now+1,l,r)); return res; } inline void Tcover(int x,int y,int z) { while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y); cover(1,id[top[x]],id[x],z); x=father[top[x]]; } if(depth[x]>depth[y]) swap(x,y); cover(1,id[x]+1,id[y],z); //lca不能被更新！ } inline void Tadd(int x,int y,int z) { while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y); add(1,id[top[x]],id[x],z); x=father[top[x]]; } if(depth[x]>depth[y]) swap(x,y); add(1,id[x]+1,id[y],z); } inline int Qmax(int x,int y) { int ans=0; while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y); ans=max(ans,query(1,id[top[x]],id[x])); x=father[top[x]]; } if(depth[x]>depth[y]) swap(x,y); return max(ans,query(1,id[x]+1,id[y])); } int main() { read(n); for(int i=1,u,v,w;i<=n-1;i++) { read(u),read(v),read(w); addedge(u,v,w); addedge(v,u,w); } dfs1(1,0); dfs2(1,1); build(1,1,n); string s; while(cin>>s) { int u,v,w; if(s=="Stop") return 0; if(s=="Max") { read(u),read(v); cout<<Qmax(u,v)<<'\n'; } if(s=="Change") //单点修改 { read(u),read(v); u*=2; //加的双向边 u=depth[edge[u].from]>depth[edge[u].to]?edge[u].from:edge[u].to; cover(1,id[u],id[u],v); } if(s=="Add") //区间加 { read(u),read(v),read(w); Tadd(u,v,w); } if(s=="Cover") { read(u),read(v),read(w); Tcover(u,v,w); } } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9865938.html
相关资源：各显卡算力对照表！