解析

不難得到最優策略：先盡可能的快的送死直到路徑暢通無組，然后一口氣沖到t點。
現在的難點就在于如何盡可能的快的送掉特定的次數。
不難發現，花費時間關于死亡次數的函數必然是一個下凸包。

設 $f_{x,i}$ 表示子樹內距離 $x$ 不超過 i 的節點的最大 $w$。
設當前詢問 $(s,t)$ 路徑上需要的最大死亡次數為 $mx$，找到最小的 i 滿足 $f_{s,i}\ge w$，那么答案可以寫成 $mx?i?{\sum }_{j=1}^{i?1}{f}_{s,j}$。
不難想到利用線段樹來維護這個 $f$。
但是暴力合并顯然復雜度無法接受，由于這個距離與深度有關，考慮長鏈剖分，一條長鏈的點共用一個線段樹。每次合并的時候把兒子的整條鏈一個點一個點暴力修改上去即可。

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return f*x; }const int N=3e5+100; int n,m; struct edge{int to,nxt; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y){p[++cnt]=(edge){y,fi[x]};fi[x]=cnt; } #define mid ((l+r)>>1) #define ls (k<<1) #define rs (k<<1|1) struct Segment_Tree{int n;vector<ll>mn,laz,sum;void init(int L){mn.resize(L<<2);laz.resize(L<<2);sum.resize(L<<2);n=L-1;}inline void pushup(int k){mn[k]=min(mn[ls],mn[rs]);sum[k]=sum[ls]+sum[rs];return;}inline void add(int k,int l,int r,ll w){mn[k]=w;sum[k]=(r-l+1)*w;laz[k]=w;}inline void pushdown(int k,int l,int r){ll o=laz[k];laz[k]=0;if(!o) return;add(ls,l,mid,o);add(rs,mid+1,r,o);return;}void change(int k,int l,int r,int x,int y,ll w){if(x<=l&&r<=y){add(k,l,r,w);return;}pushdown(k,l,r);if(x<=mid) change(ls,l,mid,x,y,w);if(y>mid) change(rs,mid+1,r,x,y,w);pushup(k);}ll asksum(int k,int l,int r,int x,int y){if(x<=l&&r<=y) return sum[k];pushdown(k,l,r);ll res(0);if(x<=mid) res+=asksum(ls,l,mid,x,y);if(y>mid) res+=asksum(rs,mid+1,r,x,y);return res;}int find(int k,int l,int r,int w){//last pl that val<wif(l==r) return l;pushdown(k,l,r);if(mn[rs]<w) return find(rs,mid+1,r,w);else return find(ls,l,mid,w);}inline ll Asksum(int l,int r){return asksum(1,0,n,l,r);}inline int Find(int w){return find(1,0,n,w);}inline void update(int pl,int w){if(mn[1]>w) return;int ed=Find(w);if(pl<=ed) change(1,0,n,pl,ed,w); return;} }tr[N];int w[N]; int len[N],dep[N],top[N],son[N],pl[N][20],mx[N][20]; void dfs(int x,int f){dep[x]=dep[f]+1;len[x]=1;if(f){pl[x][0]=f;mx[x][0]=w[f];for(int k=1;pl[x][k-1];k++){pl[x][k]=pl[pl[x][k-1]][k-1];mx[x][k]=max(mx[x][k-1],mx[pl[x][k-1]][k-1]);}}for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;dfs(to,x);if(len[to]+1>len[x]){son[x]=to;len[x]=len[to]+1;}}return; } inline int add(int x){return dep[x]-dep[top[x]]; }vector<int>v[N]; ll d[N],ans[N];void solve(int x){if(x==top[x]){tr[x].init(len[x]);}if(son[x]){top[son[x]]=top[x];solve(son[x]);}for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==son[x]) continue;top[to]=to;solve(to);for(int i=0;i<len[to];i++){tr[top[x]].update(i+1+add(x),tr[to].Asksum(i,i));}}for(int id:v[x]){int pl=tr[top[x]].Find(d[id])+1;ans[id]+=(pl-add(x))*d[id];if(add(x)<pl) ans[id]-=tr[top[x]].Asksum(add(x),pl-1);}//debug("x=%d top=%d\n",x,top[x]);tr[top[x]].update(add(x),w[x]); }inline int calc(int x,int y){int ans(0);for(int k=18;k>=0;k--){if(dep[pl[x][k]]<=dep[y]) continue;ans=max(ans,mx[x][k]);x=pl[x][k];}return ans; }int main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();for(int i=1;i<=n;i++) w[i]=read();for(int i=2;i<=n;i++) addline(read(),i);dfs(1,0);m=read();for(int i=1;i<=m;i++){int s=read(),t=read();ans[i]+=dep[t]-dep[s];v[s].push_back(i);d[i]=calc(t,s);}top[1]=1;solve(1);for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); }

總結

以上是生活随笔為你收集整理的YBTOJ：最短时间（长链剖分、线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。