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;
}