倍增什么的最慢了，常数太大了
我们可以上树剖啊
但是如果用树剖来查询树上两点之间的最小边权的话，可能只能在上一棵线段树？
那也太\(naive\)了，尽管倍增常数大，但是还是比两个\(log\)快的
那干脆重构树算了
这就是我最优解的原因了
之后发现自己的思路非常清奇，那就干脆再写一下思路吧
可能是我太傻了，并没有发现可以直接贪心，所以搞出来一种非常难写的方法
我们定义一个\(Maxn\)数组，\(Maxn[i]\)表示\(i\)次交易后最多可以携带多少枚金子
显然\(Maxn[n]=0\)，\(n\)次交易后我们不能再有金子了
之后我们倒着推出\(Maxn\)数组
首先\(Maxn[i]\)应该等于\(i\)次交易和\(i+1\)次交易之间两点的最小边权
如果\(a[i+1]<0\)，我们可以通过卖出消耗掉一些,那就说明我们可以多往后传递一些，于是就有\(Maxn[i]-|a[i+1]|<=Maxn[i+1]\)
也就是\(Maxn[i]<=Maxn[i]-a[i+1]\)
如果\(a[i+1]>0\)，我们卖出都不能了，于是就有\(Maxn[i]<=Maxn[i+1]\)
求出\(Maxn\)数组之后贪心就可以啦
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<iostream> #define re register #define maxn 100005 #define INF 9999999999 #define LL long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) struct E { int v,nxt; }e[maxn<<2]; struct g { int x,y; LL z; }G[maxn<<1]; int fa[maxn<<1]; int sum[maxn<<1],Fa[maxn<<1],top[maxn<<1],deep[maxn<<1],son[maxn<<1],head[maxn<<1]; int n,m,q,num; LL Maxn[maxn]; int c[maxn<<1]; LL a[maxn],b[maxn]; LL val[maxn<<2]; inline LL read() { char c=getchar(); LL x=0,r=1; while(c<'0'||c>'9') {if(c=='-') r=-1;c=getchar();} while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar(); return x*r; } inline int find(int x) { if(x==fa[x]) return x; return fa[x]=find(fa[x]); } inline void add_edge(int x,int y) { e[++num].v=y; e[num].nxt=head[x]; head[x]=num; } void dfs1(int x) { sum[x]=1; int maxx=-1; for(re int i=head[x];i;i=e[i].nxt) if(!deep[e[i].v]) { deep[e[i].v]=deep[x]+1; Fa[e[i].v]=x; dfs1(e[i].v); sum[x]+=sum[e[i].v]; if(sum[e[i].v]>maxx) maxx=sum[e[i].v],son[x]=e[i].v; } } void dfs2(int x,int topf) { top[x]=topf; if(!son[x]) return; dfs2(son[x],topf); for(re int i=head[x];i;i=e[i].nxt) if(deep[e[i].v]>deep[x]&&son[x]!=e[i].v) dfs2(e[i].v,e[i].v); } inline int LCA(int x,int y) { while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) std::swap(x,y); x=Fa[top[x]]; } if(deep[x]<deep[y]) return x; return y; } inline int cmp(g a,g b) { return a.z>b.z; } signed main() { n=read(),m=read(),q=read(); for(re int i=1;i<=n;i++) b[i]=read(); for(re int i=1;i<=n;i++) a[i]=read(); for(re int i=1;i<=m;i++) G[i].x=read(),G[i].y=read(),G[i].z=read(); for(re int i=1;i<=n*2;i++) c[i]=i; if(q>=1) { int pre=read(),X; for(re int i=1;i<q;i++) { X=read(); c[X]=pre; } } std::sort(G+1,G+m+1,cmp); for(re int i=1;i<=n*2;i++) if(c[i]==i) fa[i]=i; int cnt=n; for(re int i=1;i<=m;i++) { int xx=find(c[G[i].x]); int yy=find(c[G[i].y]); if(xx==yy) continue; add_edge(++cnt,xx),add_edge(cnt,yy); add_edge(xx,cnt),add_edge(yy,cnt); val[cnt]=G[i].z; fa[xx]=cnt,fa[yy]=cnt; } deep[cnt]=1; dfs1(cnt); dfs2(cnt,cnt); Maxn[n]=0; for(re int i=n-1;i;i--) { int lca=LCA(c[b[i]],c[b[i+1]]); Maxn[i]=val[lca]; if(lca==c[b[i]]) Maxn[i]=INF; if(a[b[i+1]]<0) Maxn[i]=min(Maxn[i+1]-a[b[i+1]],Maxn[i]); else Maxn[i]=min(Maxn[i],Maxn[i+1]); } LL now=0; for(re int i=1;i<=n;i++) { if(a[b[i]]>0) now=min(Maxn[i],a[b[i]]+now); else { printf("%lld\n",min(now,-a[b[i]])); now+=a[b[i]]; now=max(now,0); } } return 0; }原文链接：https://blog.csdn.net/weixin_30848775/article/details/99090648?ops_request_misc=&request_id=19f97ff6b2584a84b2f1c6aacd15146d&biz_id=&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~koosearch~default-10-99090648-null-null.268%5Ev1%5Econtrol&utm_term=%E8%A5%BF%E5%AE%89%E6%91%A9%E6%89%98%E8%BD%A6
