传送门

题目描述：

wyf非常喜欢树。一棵有根数树上有N个节点，1号点是他的根，每条边都有一个距离，而wyf是个爱问奇怪问题的熊孩子，他想知道对于某个点x,以x为根的子树上，所有与x距离大于等于k的点与x的距离之和。

输入描述:

第一行一个正整数N
接下来N-1描述这棵树，每行两个数第i行两个数p和D表示树上有一条p到i+1长度为D的边。(p<=i)
下面一行一个正整数Q表示wyf的询问次数。
接下来Q行每行两个正整数x和k。 (1<=N,Q<=2x10^5,1<=D,K<=10^6)

输出描述:

对于每次询问x,k输出以x为根的子树上，所有与x距离大于等于k的点与x的距离之和。(若不存在这样的点，则输出应为0)

解题思路：  题目上询问的是子树上的点，很容易想到DFS序，因为要用到时间戳，就想到了可持久化线段树。。
因为一棵子树的DFS序恰好是一个区间，利用可持久化线段树就很容易查询了。
维护 区间所有值的和 和 结点的个数，询问时答案 = 距离大于等于 dis[x]+k 所有值的和 - cnt * dis[ x ]。

代码：
 

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>

#define MT(a, b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai = acos(-1.0);
const double E = 2.718281828459;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;

int root[maxn], times;        /// 根结点  动态树时间戳
int head[maxn], sign;         /// 边
int in[maxn], out[maxn], t;   /// DFS序
ll dis[maxn];                 ///距离根节点的距离

struct node {
    int ls, rs;
    ll cnt, sum;
} p[maxn * 40];

struct node_e {
    int e;
    ll c;
    int p;
} load[maxn << 1];

void add_edge(int s, int e, ll c) {
    load[++sign] = node_e{e, c, head[s]};
    head[s] = sign;
}

void insert(int &now, int old, ll l, ll r, ll x) {
    now = ++times;
    p[now] = p[old], p[now].sum += x, p[now].cnt++;
    if (l == r)
        return;
    ll mid = (l + r) >> 1LL;
    if (x <= mid) insert(p[now].ls, p[old].ls, l, mid, x);
    else insert(p[now].rs, p[old].rs, mid + 1, r, x);
}

ll sum_dis, sum_cnt;

void query(int sta, int end, ll l, ll r, ll x) {
    if (l >= x) {
        sum_dis += p[end].sum - p[sta].sum;
        sum_cnt += p[end].cnt - p[sta].cnt;
        return;
    }
    ll mid = (l + r) >> 1;
    if (x <= mid) {
        sum_dis += p[p[end].rs].sum - p[p[sta].rs].sum;
        sum_cnt += p[p[end].rs].cnt - p[p[sta].rs].cnt;
        query(p[sta].ls, p[end].ls, l, mid, x);
    } else
        query(p[sta].rs, p[end].rs, mid + 1, r, x);
}

void dfs(int s, int pre) {
    in[s] = ++t;
    insert(root[t], root[t - 1], (ll) 1, (ll) 1e11, dis[s]);
    for (int i = head[s], e; ~i; i = load[i].p) {
        e = load[i].e;
        if (e ^ pre) {
            dis[e] = dis[s] + load[i].c;
            dfs(e, s);
        }
    }
    out[s] = t;
}

void init() {
    t = times = sign = 0;
    memset(head, -1, sizeof(head));
    memset(p, 0, sizeof(p));
    memset(root, 0, sizeof(root));
    memset(dis, 0, sizeof(dis));
}

int main() {
    init();
    int n, op, s, x;
    ll c, k;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d %lld", &s, &c);
        add_edge(s, i + 1, c);
        add_edge(i + 1, s, c);
    }
    dfs(1, -1);
    scanf("%d", &op);
    while (op--) {
        sum_cnt = sum_dis = 0;
        scanf("%d %lld", &x, &k);
        k = k + dis[x];
        query(root[in[x]], root[out[x]], 1LL, (ll) 1e11, k);
        printf("%lld\n", sum_dis - sum_cnt * dis[x]);
    }
}