题目链接：http://codeforces.com/contest/1110/problem/F
题目大意：
统计查询类题目，给定一颗树，树边有权重，
查询格式是:x,y,z,查询x节点到[y,z]区间中的叶节点的
最短路径长度是多少。其树的产生形式严格遵循DFS序形式。
题目分析：
这道题我是瞄了眼题解的思路的，才知道有个换根的性质。
大体是这样的：
首先考虑所有的x都是1根节点，那么我们只要把叶节点插入到线段树里面查询即可。
然后考虑状态转移，即dp[u]与dp[v]的关系，
把以u为根节点的线段树的状态，转移到以v为根节点的线段树的状态，
不难发现，v子树中所有点其距离都减少了e(u,v)，其余的都增加了e(u,v)，
那么这个就用线段树维护区间性质，其子树的区间可以用DFS序事先维护出来，
然后我们用离线操作按x来存储查询，最后深搜的时候统计答案即可。
详见代码，大部分都是模板操作，最终的思路是在solve函数里面。
时间复杂度为O(mlogn+n).
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=5e5+5;
const int ub=1e6;
const double inf=1e-4;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：
统计查询类题目，给定一颗树，树边有权重，
查询格式是:x,y,z,查询x节点到[y,z]区间中的叶节点的
最短路径长度是多少。其树的产生形式严格遵循DFS序形式。题目分析：
这道题我是瞄了眼题解的思路的，才知道有个换根的性质。
大体是这样的：
首先考虑所有的x都是1根节点，那么我们只要把叶节点插入到线段树里面查询即可。
然后考虑状态转移，即dp[u]与dp[v]的关系，
把以u为根节点的线段树的状态，转移到以v为根节点的线段树的状态，
不难发现，v子树中所有点其距离都减少了e(u,v)，其余的都增加了e(u,v)，
那么这个就用线段树维护区间性质，其子树的区间可以用DFS序事先维护出来，
然后我们用离线操作按x来存储查询，最后深搜的时候统计答案即可。
详见代码，大部分都是模板操作，最终的思路是在solve函数里面。
时间复杂度为O(mlogn+n).
*/
int n,q,x,y,z;
int pl[maxn],pr[maxn],d[maxn],tot=0;///DFS序
vector<pair<int,int>> g[maxn];///存储边关系
struct Q{int y,v,id;};
vector<Q> qy[maxn];
ll tree[maxn<<2],lazy[maxn<<2];
ll dis[maxn],ans[maxn],INF=1e18;
void build(lrt){lazy[rt]=0,tree[rt]=INF;if(l==r){if(d[l]==1) tree[rt]=dis[l];return;}int mid=l+r>>1;build(lson),build(rson);tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}
void pushdown(lrt){if(lazy[rt]){lazy[rt<<1]+=lazy[rt];lazy[rt<<1|1]+=lazy[rt];tree[rt<<1]+=lazy[rt];tree[rt<<1]=min(tree[rt<<1],INF);tree[rt<<1|1]+=lazy[rt];tree[rt<<1|1]=min(tree[rt<<1|1],INF);lazy[rt]=0;}
}
void update(lrt,int L,int R,int v){if(L>R) return ;if(L<=l&&r<=R){if(tree[rt]!=INF){tree[rt]-=v;lazy[rt]-=v;}return ;}pushdown(root);int mid=l+r>>1;if(L<=mid) update(lson,L,R,v);if(mid<R) update(rson,L,R,v);tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}
ll query(lrt,int L,int R){if(L<=l&&r<=R){return tree[rt];}pushdown(root);int mid=l+r>>1;ll ret=INF;if(L<=mid) ret=min(ret,query(lson,L,R));if(mid<R) ret=min(ret,query(rson,L,R));return ret;
}
void dfs(int u,int fa){pl[u]=++tot;for(int i=0;i<g[u].size();i++){int v=g[u][i].fi,len=g[u][i].se;if(v==fa) continue;dis[v]=dis[u]+len;dfs(v,u);}pr[u]=tot;
}
void solve(int u,int fa){rep(i,0,qy[u].size()){int y=qy[u][i].y,v=qy[u][i].v,id=qy[u][i].id;ans[id]=query(1,n,1,y,v);}for(int i=0;i<g[u].size();i++){int v=g[u][i].fi,len=g[u][i].se;if(v==fa) continue;update(1,n,1,pl[v],pr[v],len);update(1,n,1,1,pl[v]-1,-len),update(1,n,1,pr[v]+1,n,-len);solve(v,u);update(1,n,1,pl[v],pr[v],-len);update(1,n,1,1,pl[v]-1,len),update(1,n,1,pr[v]+1,n,len);}
}
int main(){scanf("%d%d",&n,&q);rep(i,2,n+1){scanf("%d%d",&x,&y);g[i].push_back(make_pair(x,y));g[x].push_back(make_pair(i,y));d[i]++,d[x]++;}rep(i,0,q){scanf("%d%d%d",&x,&y,&z);qy[x].push_back(Q{y,z,i});}dis[1]=0,tot=0;dfs(1,-1),build(1,n,1);solve(1,-1);rep(i,0,q) printf("%lld\n",ans[i]);return 0;
}