F dfs序+线段树

首先dfs求出：

dep：每个节点深度

siz：每个节点子树大小

dfn：每个节点的dfs序

val：每个节点到根节点的路径和

一个节点u往下d次的最大边权和，就是找深度为dep[u] + d的点中，在u的子树中的，最大的val[i]。然后再减去val[u]。

判断是否在u的子树中，即判断节点的dfs序是否属于$[dfn[u],dfn[u]+siz[u]-1]$。如果对每个深度开一个线段树，那就是一个单点修改+区间查询最大值。

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

`