Codeforces Global Round 1 F. Nearest Leaf（线段树+离线操作）*

题目链接：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;
}