题目描述： 每次询问树上的一段路径，求出路径上点权最小值。
修改操作，选择一段路径使路径上的每个点又新加入一个数字为 a×dis+b。
每个点的初始数字为123456789123456789。
可以树链剖分，对于a*dis+b的式子，可以转化成一条线段，于是问题转化成动态维护区间内线段的最低点。
可以用标记永久化线段树来维护。
#include<cstdio>#include<iostream>#include<cstring>#include<vector>#define ll long longusing namespace std;const ll inf=123456789123456789;const int maxn=101000;vector<int> f[maxn];vector<ll> g[maxn];int son[maxn],deep[maxn],sz[maxn],top[maxn],id[maxn],fa[maxn],pos[maxn],cnt;ll ans,dist[maxn];int n,m,x,y,z,op;ll a,b;struct tree{ ll a,b,mn;};tree T[maxn*4];void dfs1(int u,int fath,int dep,ll dis){ fa[u]=fath;deep[u]=dep; son[u]=0;sz[u]=1;dist[u]=dis; for(int i=0;i<f[u].size();i++) { int v=f[u][i]; if(v==fath) continue; dfs1(v,u,dep+1,dis+g[u][i]); sz[u]+=sz[v]; if(sz[son[u]]<sz[v]) son[u]=v; }}void dfs2(int u,int tp){ pos[u]=++cnt; id[cnt]=u;top[u]=tp; if(son[u]) dfs2(son[u],tp); for(int i=0;i<f[u].size();i++) { int v=f[u][i]; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); }}int lca(int a,int b){ while(top[a]!=top[b]) { if(deep[top[a]]<deep[top[b]]) swap(a,b); a=fa[top[a]]; } return deep[a]<deep[b] ? a : b ; }ll calc(ll a,ll b,ll x){ return a*dist[id[x]]+b; } void build(int rt,int l,int r){ T[rt].a=0,T[rt].b=inf,T[rt].mn=inf; if(l==r) return ; int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r);}void update(int rt,int l,int r,ll a,ll b){ ll yl=calc(a,b,l),yr=calc(a,b,r),xl=calc(T[rt].a,T[rt].b,l),xr=calc(T[rt].a,T[rt].b,r); if(xl<=yl&&xr<=yr) return; if(xl>=yl&&xr>=yr) {T[rt].a=a;T[rt].b=b;return;} int mid=(l+r)>>1; ll xm=calc(T[rt].a,T[rt].b,mid),ym=calc(a,b,mid); if(xm>=ym) {swap(T[rt].a,a);swap(T[rt].b,b);swap(xl,yl);swap(xr,yr);swap(xm,ym);} if(xl>=yl) update(rt<<1,l,mid,a,b); else update(rt<<1|1,mid+1,r,a,b);}inline void add(int rt,int l,int r,int L,int R,ll a,ll b){ T[rt].mn=min(T[rt].mn,min(calc(a,b,L),calc(a,b,R))); if(l==L&&r==R){update(rt,l,r,a,b);return;} int mid=(l+r)>>1; if(R<=mid) add(rt<<1,l,mid,L,R,a,b); else if(L>mid) add(rt<<1|1,mid+1,r,L,R,a,b); else add(rt<<1,l,mid,L,mid,a,b),add(rt<<1|1,mid+1,r,mid+1,R,a,b);}inline void query(int rt,int l,int r,int L,int R){ ans=min(ans,min(calc(T[rt].a,T[rt].b,L),calc(T[rt].a,T[rt].b,R))); //cout<<calc(T[rt].a,T[rt].b,L)<<" "<<calc(T[rt].a,T[rt].b,R)<<endl; if(l==L&&r==R) {ans=min(ans,T[rt].mn);return;} int mid=(l+r)>>1; if(R<=mid) query(rt<<1,l,mid,L,R); else if(L>mid) query(rt<<1|1,mid+1,r,L,R); else query(rt<<1,l,mid,L,mid),query(rt<<1|1,mid+1,r,mid+1,R);}inline void workadd(int x,int y,ll a,ll b){ while(top[x]!=top[y]) { add(1,1,n,pos[top[x]],pos[x],a,b); x=fa[top[x]]; } add(1,1,n,pos[y],pos[x],a,b);}inline void workquery(int x,int y){ while(top[x]!=top[y]) { query(1,1,n,pos[top[x]],pos[x]); x=fa[top[x]]; } query(1,1,n,pos[y],pos[x]); }int main(){ scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { scanf("%d%d%d",&x,&y,&z); f[x].push_back(y);f[y].push_back(x); g[x].push_back(z);g[y].push_back(z); } dfs1(1,1,0,0); dfs2(1,1); build(1,1,n); for(int i=1;i<=m;i++) { scanf("%d%d%d",&op,&x,&y); if(op==1) { scanf("%lld%lld",&a,&b); int LCA=lca(x,y); workadd(x,LCA,-a,a*dist[x]+b); workadd(y,LCA,a,a*(dist[x]-dist[LCA]*2)+b); } else { ans=inf; int LCA=lca(x,y); workquery(x,LCA);workquery(y,LCA); PRintf("%lld/n",ans); } } return 0;}新闻热点
疑难解答
