https://ac.nowcoder.com/acm/contest/95016/F
题意：给一棵带边权的树，q次查询，每次查询求u节点往下d次的最大边权和。

线段树做法

预处理val，代表根节点到该节点的距离之和，即求深度为dep[u]+d的节点中，在u的子树中的，最大的val。答案是val[i] - val[u]。
dfs序将子树查询转换为区间查询最大值，往里填数据实际上是单点修改。因此对每个深度开一个线段树可解决问题。

#include<bits/stdc++.h>


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int n,q;
vector<vector<pll>> g;

const int N = 5e6+10;
const int M = 1e5+10;
ll maxv[N],ls[N],rs[N],rt[2*M],cnt;
ll val[M];//根节点到该点的权值和
int dfn[M],rnk[M];
int dep[M],siz[M];

void dfs(int u,int fa){
    dfn[u] = ++*dfn;
    rnk[dfn[u]] = u;
    siz[u] = 1;
    for(auto [v,w]:g[u]){
        if(v==fa) continue;
        dep[v] = dep[u]+1;
        val[v] = val[u]+w;
        dfs(v,u);
        siz[u] += siz[v];
    } 
}

void pushup(int u){
    maxv[u] = max(maxv[ls[u]],maxv[rs[u]]);
}
ll modify(int u,int l,int r,int co,ll val){
    if(!u) u = ++ cnt;
    if(l==r){
        maxv[u] = max(maxv[u],val);
        return u;
    }
    int mid = l+r>>1;
    if(co<=mid){
        ls[u] = modify(ls[u],l,mid,co,val);
    }
    else{
        rs[u] = modify(rs[u],mid+1,r,co,val);
    }
    pushup(u);
    return u;
}
ll query(int u,int l,int r,int x,int y){
    if(!u) return -1e9;
    if(x>r || y<l) return -1e9;
    if(x<=l && y>=r) return maxv[u];
    int mid = l+r>>1;
    return max(query(ls[u],l,mid,x,y),query(rs[u],mid+1,r,x,y));
}

void solve(){
    cin>>n;
    g = vector<vector<pll>>(n+1);
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dep[1] = 1;
    dfs(1,0);
    for(int i=1;i<=n;i++){
        rt[dep[i]] = modify(rt[dep[i]],1,n,dfn[i],val[i]);
    }
    int q;
    cin>>q;
    while(q--){
        int u,d; cin>>u>>d;
        ll ans = query(rt[dep[u] + d],1,n,dfn[u],dfn[u]+siz[u]-1);
        if(ans<=0) cout<<-1<<endl;
        else{
            cout<<ans - val[u]<<endl;
        }
    }
}


int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}

长链剖分优化dp做法

略有点板。但是一开始写的时候被一个问题卡出了：状态应该是dp[i][j]代表节点i往下j次的最大权值和，但是继承重儿子状态的时候，必须把重链上所有值都加一个到重儿子的边权，但是这样就不是O(1)继承了。
解决方法：显然是要加一个偏置，如加一个到根节点权值和的偏置。虽然想到了，但是太想把dp[i][j]直接处理成i节点往下j次的最大权值和，反而还是被卡住了。实际上和上面线段树做法一样，处理dp[i][j]为节点i，往下j次所到达的，最大的，根节点到该点的权值和即可。
btw，这个做法要离线询问，因为递归返回后，节点的状态会被父节点破坏。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

const int  N = 1e5+10;

int n;
ll dep[N],mx[N],son[N],fa[N];
ll w[N];
ll len[N],top[N];
ll d[N];
ll dfn[N],val[N],*dp[N];
//dp[i][j] i节点往下j次，得到的最大权值和
vector<vector<pll>> g;

void dfs1(int u){
    son[u] = -1; mx[u] = dep[u];
    for(auto [v,x]:g[u]){
        if(!dep[v]){
            dep[v] = dep[u]+1;
            fa[v] = u;
            w[v] = w[u] + x;
            dfs1(v);
            if(son[u]==-1||mx[v] > mx[son[u]]) son[u] = v,mx[u] = mx[v];
        }
    }
}
void dfs2(int u,int t){
    top[u] = t; len[u] = mx[u] - dep[t] + 1;
    d[u] = mx[u] - dep[u];
    dfn[u] = ++*dfn;    dp[u] = val + dfn[u];
    if(son[u]!=-1) dfs2(son[u],t);
    for(auto [v,w]:g[u]){
        if(v==son[u]||v==fa[u]) continue;
        dfs2(v,u);
    }
}
vector<vector<pii>> query;
vector<ll> ans;

void getans(int u){
    if(son[u]!=-1){
        getans(son[u]);
        //u到重儿子长链底端的 都要+w[u]
    }
    dp[u][0] = w[u];
    for(auto [v,x]:g[u]){
        if(v==fa[u]||v==son[u]) continue;
        getans(v);
        for(int i=0;i<=d[v];i++){
            dp[u][i+1] = max(dp[u][i+1],dp[v][i]);      
        }
    }
    for(auto [de,id]:query[u]){
        if(de > d[u]) ans[id] = -1;
        else ans[id] = dp[u][de]-w[u];
    }
}

void solve(){
    cin>>n;
    g = vector<vector<pll>>(n+1);
    for(int i=0;i<n-1;i++){
        int a,b,w;
        cin>>a>>b>>w;
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }
    dep[1] = 1;
    dfs1(1);
    dfs2(1,1);
    int q; cin>>q;
    query = vector<vector<pii>>(n+1);
    ans = vector<ll>(q+1);

    for(int i=1;i<=q;i++){
        int u,d; cin>>u>>d;
        query[u].push_back({d,i});
    }
    getans(1);
    for(int i=1;i<=q;i++)
        cout<<ans[i]<<endl;

}

int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}