自己搞的算法超时了。。但是思路没什么问题：用线段树维护每个点到叶子节点的距离即可
/* 线段树维护区间最小值，每次向下访问，就把访问到的点对应的区间段减去边权 到另一颗子树访问时，向上回溯时加上减去的边权即可; */ #include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 500050 #define INF 0x3f3f3f3f3f3f3f3f struct Query{ int x,l,r,id; bool operator<(const Query &y)const{return x<y.x;} }Q[maxn]; int q,n,fa[maxn],r[maxn],leaf[maxn]; ll dep[maxn],w[maxn],ans[maxn]; /*线段树部分*/ #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 ll Min[maxn<<2],add[maxn<<2]; inline void pushup(int rt){Min[rt]=min(Min[rt<<1],Min[rt<<1|1])+add[rt];} void build(int l,int r,int rt){ add[rt]=0; if(l==r){Min[rt]=leaf[l]?dep[l]:INF;return;}//不是叶子节点就是无限大 int m=l+r>>1; build(lson); build(rson); pushup(rt); } void Add(int L,int R,int l,int r,int rt,int val){ if(L<=l && R>=r){ add[rt]+=val;Min[rt]+=val;return; } int m=l+r>>1; if(L<=m) Add(L,R,lson,val); if(R>m) Add(L,R,rson,val); pushup(rt); } ll query(int L,int R,int l,int r,int rt){ if(L<=l && R>=r)return Min[rt]; int m=l+r>>1; ll res=INF; if(L<=m)res=min(res,query(L,R,lson)); if(R>m)res=min(res,query(L,R,rson)); return res+add[rt]; } int main(){ cin>>n>>q; memset(leaf,1,sizeof leaf); for(int i=1;i<=n;i++)r[i]=i; for(int i=2;i<=n;i++){ cin>>fa[i]>>w[i]; leaf[fa[i]]=0; dep[i]=dep[fa[i]]+w[i]; } for(int i=n;i>=2;i--) r[fa[i]]=max(r[fa[i]],r[i]); for(int i=0;i<q;i++) cin>>Q[i].x>>Q[i].l>>Q[i].r,Q[i].id=i; sort(Q,Q+q); build(1,n,1); int x=1,qi=0;//从根开始遍历 ll offset=0;//用来记录回溯的 while(1){ while(Q[qi].x==x && qi<q){ ans[Q[qi].id]=query(Q[qi].l,Q[qi].r,1,n,1)+offset; ++qi; } if(x<n){ int y=x+1; while(x!=fa[y]){ Add(x,r[x],1,n,1,2*w[x]); offset-=w[x]; x=fa[x]; } x=y; Add(x,r[x],1,n,1,-2*w[x]); offset+=w[x]; } else break; } for(int i=0;i<q;i++)printf("%lld ",ans[i]); }
这是cf上的代码
#include<bits/stdc++.h> #define maxn 1000005 #define F first #define S second using namespace std; typedef long long ll; const ll INF=1e18; typedef pair<ll,ll> pi; typedef pair<int,pi> pii; vector <pi> h[maxn]; vector <pii> q[maxn]; ll ans[maxn],a[maxn],dep[maxn],st[maxn*4],add[maxn*4]; int n,m,Q,id,l[maxn],r[maxn]; void build(int o,int l,int r){ if (l==r) st[o]=a[l]; else { int m=l+((r-l)>>1); build(o<<1,l,m); build((o<<1)|1,m+1,r); st[o]=min(st[o<<1],st[(o<<1)|1]); } } void pushup(int o){ st[o]=min(st[o<<1],st[o<<1|1]); } void pushdown(int o,int l,int r){ if (add[o]){ add[o<<1]+=add[o]; add[o<<1|1]+=add[o]; int m=l+((r-l)>>1); st[o<<1]+=add[o]; st[o<<1|1]+=add[o]; add[o]=0; } } void update(int o,int l,int r,int ql,int qr,ll addv){ if (ql<=l&&qr>=r) { add[o]+=addv; st[o]+=addv; return; } pushdown(o,l,r); int m=l+((r-l)>>1); if (ql<=m) update(o<<1,l,m,ql,qr,addv); if (qr>=m+1) update(o<<1|1,m+1,r,ql,qr,addv); pushup(o); } ll query(int o,int l,int r,int ql,int qr){ if(ql<=l&&qr>=r) return st[o]; pushdown(o,l,r); int m=l+((r-l)>>1); ll ans=INF; if (ql<=m) ans=min(ans,query(o<<1,l,m,ql,qr)); if (qr>=m+1) ans=min(ans,query(o<<1|1,m+1,r,ql,qr)); return ans; } void dfs0(int u){ ++id; assert(u==id); l[u]=id; if (!h[u].size()) a[u]=dep[u]; else a[u]=INF; for (int i=0;i<h[u].size();i++){ int v=h[u][i].F; dep[v]=dep[u]+h[u][i].S; dfs0(v); } r[u]=id; } void dfs(int u){ for (int i=0;i<q[u].size();i++) ans[q[u][i].F]=query(1,1,n,q[u][i].S.F,q[u][i].S.S)+dep[u]; for (int i=0;i<h[u].size();i++){ int v=h[u][i].F; update(1,1,n,l[v],r[v],-h[u][i].S*2); dfs(v); update(1,1,n,l[v],r[v],h[u][i].S*2); } } int main(){ cin >> n >> Q; for (int i=2;i<=n;i++){ ll u,v; scanf("%I64d%I64d",&u,&v); h[u].push_back((pi){i,v}); } for (int i=1;i<=Q;i++){ int u,v,w; scanf("%d%d%d",&w,&u,&v); q[w].push_back((pii){i,(pi){u,v}}); } dfs0(1); build(1,1,n); dfs(1); for (int i=1;i<=Q;i++) printf("%I64d ",ans[i]); return 0; }