可在线版题解

既然有离线的树状数组版本（时间空间非常优秀）题解，那怎么少的了可在线的主席树版本呢（时间空间不是很优秀）。

前置芝士

序，离散化，主席树

思路

1.像这种对某个子树进行查询的操作，并且多组查询，很明显需要将整棵树拍扁（就是求 序），这样我们就可以将子树化为一个连续的区间进行维护。
2.题目要求子树内距离该子树的根 的距离大于 的距离和，我们可以先求出所有点到根 的距离，这样一棵子树内某个点 距离该子树根 的距离就一目了然了，就是。然后我们求出子树内满足 即可。但是这每次询问枚举一整棵子树复杂度高达 ,非常不合理，我们需要维护子树。
3.其实也很明显，维护一个子树内的每个离根的不同距离 的前缀和，最大值可能高达，我们需要离散化距离，不过得记住确切距离是多少（毕竟离散化距离后最多只有 种，同时记住每个位置的真实距离，那么题目所求便是某个区间（代表某棵子树）的大于某个值的后缀距离和，还没求完，才求一半)。
4.那主席树维护除了维护刚才提到的后缀距离和，还要维护后缀点数和，因为答案是
所以查询时返回二元组即可。

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const int maxn=2e5+5;

ll ds[maxn],pos[maxn],k;
ll lc[maxn<<5],rc[maxn<<5],sum[maxn<<5],ti[maxn<<5],rt[maxn],now;//sum是距离和，ti是点数和。
ll n,q,x,u,v,w,cnt,p;
struct node{
    ll id,st,en,dis;
    inline bool operator<(const node&x)const{
        return st<x.st;
    }
}dfn[maxn];
vector<P>ed[maxn];

void dfs(int x,int fa,ll d)
{
    dfn[x].id=x; dfn[x].st=dfn[x].en=++cnt; dfn[x].dis=ds[x]=d;
    for(auto y:ed[x])
    {
        if(y.first==fa)continue;
        dfs(y.first,x,d+y.second);
        dfn[x].en=max(dfn[x].en,dfn[y.first].en);
    }
    return;
}

void build(ll&t,int l,int r)
{
    t=++now;
    if(l==r)return;
    int mid=l+r>>1;
    build(lc[t],l,mid);
    build(rc[t],mid+1,r);
    return;
}

int update(int o,int l,int r,int x,ll y)
{
    int t=++now;
    lc[t]=lc[o]; rc[t]=rc[o]; sum[t]=sum[o]+y; ti[t]=ti[o]+1; 
    if(l==r)return t;
    int mid=l+r>>1;
    if(x<=mid)lc[t]=update(lc[o],l,mid,x,y);
    else rc[t]=update(rc[o],mid+1,r,x,y);
    return t;
}

P query(int u,int v,int l,int r,int x)
{
    if(l==r)return P(sum[v]-sum[u],ti[v]-ti[u]);
    int mid=l+r>>1; P res;
    if(x<=mid)//小于等于中点的右区间全加上即可
    {
        res=query(lc[u],lc[v],l,mid,x);
        res.first+=sum[rc[v]]-sum[rc[u]];
        res.second+=ti[rc[v]]-ti[rc[u]];
    }
    else res=query(rc[u],rc[v],mid+1,r,x);
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cin>>n;
    for(int i=2;i<=n;i++)
    {
        cin>>u>>v; 
        ed[u].push_back(P(i,v));
        ed[i].push_back(P(u,v));
    }
    dfs(1,0,0); sort(ds+1,ds+1+n); sort(dfn+1,dfn+1+n);
    p=unique(ds+1,ds+1+n)-ds-1; build(rt[0],1,p);
    for(int i=1;i<=n;i++)
    {
        pos[dfn[i].id]=i;
        dfn[i].dis=lower_bound(ds+1,ds+1+p,dfn[i].dis)-ds;
        rt[i]=update(rt[i-1],1,p,dfn[i].dis,ds[dfn[i].dis]);
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>u>>v; w=pos[u];
        int l=dfn[w].st,r=dfn[w].en;
        ll dd=ds[dfn[w].dis]+v;
        int pp=lower_bound(ds+1,ds+1+p,dd)-ds;
        if(pp>p)cout<<0<<"\n";
        else
        {
            P ans=query(rt[l-1],rt[r],1,p,pp);
            cout<<ans.first-ans.second*ds[dfn[w].dis]<<"\n";
        }
    }
    return 0;
}