树链剖分
线段树维护区间最小值，区间最大值
更新，对于每一个区间，找到当前区间的最小值的最大值，和要更新的值比较，如果比最大值还大，则此数对于以后的询问无任何贡献，直接返回即可，若有贡献，则一直递归到叶子节点，将最值全部更新
询问，直接询问区间最小值即可
/* Alice 和 Bob 在玩一个游戏。 游戏在一棵有 n 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 123456789123456789。 有时，Alice 会选择一条从 s 到 t 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r，若 r 与 s 的距离是 dis，那么 Alice 在点 r 上添加的数字是 a×dis+b。 有时，Bob 会选择一条从 s 到 t 的路径。他需要先从这条路径上选择一个点，再从那个点上选择一个数字。 Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。 */ #include<bits/stdc++.h> #define ll long long #define inf 123456789123456789 #define maxn 100010 using namespace std; inline int read(){ int s=0,f=1;char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1; for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0'; return s*f; } int n,m; int fa[maxn][18],dep[maxn],f[maxn]; struct edge{ int to,next,w; }G[maxn<<1]; int tot,h[maxn]; void add(int x,int y,int z){ tot++;G[tot].to=y;G[tot].next=h[x];G[tot].w=z;h[x]=tot; } int pos[maxn],sz,size[maxn],poz[maxn]; ll t[maxn<<2],dis[maxn],mx[maxn<<2]; void dfs(int x){ for(int i=1;i<=17;++i) if(dep[x]<(1<<i))break; else fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=h[x];i;i=G[i].next){ int v=G[i].to; if(dep[v])continue; dep[v]=dep[x]+1; fa[v][0]=x; dis[v]=dis[x]+G[i].w; dfs(v); size[x]+=size[v]; }size[x]++; } void dfs(int x,int ff){ pos[x]=++sz;f[x]=ff;poz[sz]=x; int mx=0; for(int i=h[x];i;i=G[i].next) if(dep[G[i].to]>dep[x]&&size[G[i].to]>size[mx]) mx=G[i].to; if(!mx)return; dfs(mx,ff); for(int i=h[x];i;i=G[i].next) if(dep[G[i].to]>dep[x]&&mx!=G[i].to) dfs(G[i].to,G[i].to); } int lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); int d=dep[x]-dep[y]; for(int i=0;i<=17;++i) if(d&(1<<i)) x=fa[x][i]; if(x==y)return x; for(int i=17;i>=0;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; if(x==y)return x; return fa[x][0]; } void build(int k,int l,int r){ if(l==r){t[k]=inf;mx[k]=inf;return;} int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); t[k]=min(t[k<<1],t[k<<1|1]); mx[k]=max(mx[k<<1],mx[k<<1|1]); } void init(){ n=read();m=read(); for(int i=1;i<n;++i){ int x=read(),y=read(),z=read(); add(x,y,z);add(y,x,z); } dep[1]=1;dfs(1); dfs(1,1); build(1,1,n); } void work1(int k,int l,int r,int x,int y,ll a,ll b,ll d1,ll d2){ if(mx[k]<=a*d1+b&&mx[k]<=a*d2+b)return; if(l==r){t[k]=a*d1+b,mx[k]=a*d1+b;return;} int mid=(l+r)>>1; if(y<=mid)work1(k<<1,l,mid,x,y,a,b,d1,d2); else if(x>mid)work1(k<<1|1,mid+1,r,x,y,a,b,d1,d2); else work1(k<<1,l,mid,x,mid,a,b,d1+dis[poz[y]]-dis[poz[mid]],d2), work1(k<<1|1,mid+1,r,mid+1,y,a,b,d1,d1+dis[poz[y]]-dis[poz[mid+1]]); t[k]=min(t[k<<1],t[k<<1|1]); mx[k]=max(mx[k<<1],mx[k<<1|1]); } void work2(int k,int l,int r,int x,int y,ll a,ll b,ll d1,ll d2){ if(mx[k]<=a*d1+b&&mx[k]<=a*d2+b)return; if(l==r){t[k]=a*d1+b,mx[k]=a*d1+b;return;} int mid=(l+r)>>1; if(y<=mid)work2(k<<1,l,mid,x,y,a,b,d1,d2); else if(x>mid)work2(k<<1|1,mid+1,r,x,y,a,b,d1,d2); else work2(k<<1,l,mid,x,mid,a,b,d1,d1+dis[poz[mid]]-dis[poz[x]]), work2(k<<1|1,mid+1,r,mid+1,y,a,b,d1+dis[poz[mid+1]]-dis[poz[x]],d2); t[k]=min(t[k<<1],t[k<<1|1]); mx[k]=max(mx[k<<1],mx[k<<1|1]); } void work(int x,int y,ll a,ll b){ int k=lca(x,y); int u=x; while(f[x]!=f[k]){ work1(1,1,n,pos[f[x]],pos[x],a,b,dis[u]-dis[x],dis[u]-dis[f[x]]);x=fa[f[x]][0]; }work1(1,1,n,pos[k],pos[x],a,b,dis[u]-dis[x],dis[u]-dis[k]); while(f[y]!=f[k]){ work2(1,1,n,pos[f[y]],pos[y],a,b,dis[u]+dis[f[y]]-2*dis[k],dis[u]+dis[y]-2*dis[k]);y=fa[f[y]][0]; }work2(1,1,n,pos[k],pos[y],a,b,dis[u]-dis[k],dis[u]+dis[y]-2*dis[k]); } ll ask(int k,int l,int r,int x,int y){ if(x<=l&&r<=y)return t[k]; int mid=(l+r)>>1; if(y<=mid)return ask(k<<1,l,mid,x,y); if(x>mid)return ask(k<<1|1,mid+1,r,x,y); return min(ask(k<<1,l,mid,x,y),ask(k<<1|1,mid+1,r,x,y)); } void work(int x,int y){ int k=lca(x,y); ll ans=inf; while(f[x]!=f[k]){ ans=min(ans,ask(1,1,n,pos[f[x]],pos[x]));x=fa[f[x]][0]; }ans=min(ans,ask(1,1,n,pos[k],pos[x])); while(f[y]!=f[k]){ ans=min(ans,ask(1,1,n,pos[f[y]],pos[y]));y=fa[f[y]][0]; }ans=min(ans,ask(1,1,n,pos[k],pos[y])); printf("%lld ",ans); } void work(){ for(int i=1;i<=m;++i){ int opt=read(); if(opt==1){ int s=read(),t=read(),a=read(),b=read(); work(s,t,a,b); }else{ int s=read(),t=read(); work(s,t); } } } int main(){ init(); work(); return 0; }