1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
| #include <bits/stdc++.h> using namespace std; #define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout) #define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++) #define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++) #define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--) #define DEBUG(x) cerr<<#x<<"="<<x<<endl #define all(x) (x).begin(),(x).end() #define cle(x) memset(x,0,sizeof(x)) #define lowbit(x) ((x)&-(x)) #define ll long long #define ull unsigned ll #define db double #define lb long db #define pb push_back #define mp make_pair #define fi first #define se second inline int read() { int x=0; char ch=getchar(); bool f=0; for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1; for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48); return f?-x:x; } #define CASET fo(___,1,read()) const int N=5e5+5; const ll inf=1ll<<60; namespace SGT{ #define lc (u<<1) #define rc (u<<1|1) #define ls lc,l,mid #define rs rc,mid+1,r ll mx[N<<2],tag[N<<2]; inline void pushtag(int u,ll x) { mx[u]+=x; tag[u]+=x; } inline void pushdown(int u) { if(!tag[u]) return; pushtag(lc,tag[u]); pushtag(rc,tag[u]); tag[u]=0; } inline void pushup(int u) { mx[u]=min(mx[lc],mx[rc]); } void add(int u,int l,int r,int L,int R,ll v) { if(L<=l&&r<=R) return pushtag(u,v); int mid=l+r>>1; pushdown(u); if(L<=mid) add(ls,L,R,v); if(mid<R) add(rs,L,R,v); pushup(u); } ll ask(int u,int l,int r,int L,int R) { if(L<=l&&r<=R) return mx[u]; pushdown(u); int mid=l+r>>1; ll ans=inf; if(L<=mid) ans=min(ans,ask(ls,L,R)); if(mid<R) ans=min(ans,ask(rs,L,R)); return ans; } void ins(int u,int l,int r,int p,ll v) { if(l==r) return (void)(mx[u]=v); int mid=l+r>>1; (p<=mid)?ins(ls,p,v):ins(rs,p,v); pushup(u); } }
struct query{ int l,r,id; }; vector<query> q[N]; vector<int> leaf; int n,m,fa[N]; ll ans[N],now; int ver[N],val[N],ne[N],head[N],tot=1; inline void add(int x,int y,int z) { ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot; } int le[N],ri[N]; void dfs(int u) { for(auto x:q[u]) ans[x.id]=SGT::ask(1,1,n,x.l,x.r)+now; for(int i=head[u],v;i;i=ne[i]) { v=ver[i]; now+=val[i]; SGT::add(1,1,n,le[v],ri[v],-val[i]*2); dfs(v); now-=val[i]; SGT::add(1,1,n,le[v],ri[v],val[i]*2); } } void pre(int u,ll now) { le[u]=n+1,ri[u]=0; for(int i=head[u],v;i;i=ne[i]) { v=ver[i]; pre(v,now+val[i]); le[u]=min(le[u],le[v]); ri[u]=max(ri[u],ri[v]); } if(!head[u]) le[u]=ri[u]=u,SGT::ins(1,1,n,u,now); else SGT::ins(1,1,n,u,inf); } int main() { n=read(); m=read(); fo(i,2,n) { fa[i]=read(); add(fa[i],i,read()); } fo(i,1,n) if(!head[i]) leaf.pb(i); pre(1,0); int v,l,r; fo(i,1,m) { v=read(); l=read(); r=read(); l=lower_bound(all(leaf),l)-leaf.begin(); r=upper_bound(all(leaf),r)-leaf.begin()-1; if(l>r) continue; q[v].pb((query){leaf[l],leaf[r],i}); } dfs(1); fo(i,1,m) printf("%lld\n",ans[i]); return 0; }
|