Blackops

初心易得，始终难守

0%

Wannafly挑战赛4 D 树的距离（DFS序+离线+树状数组）

发表于 分类于 ， ，

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述
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<=2x105,1<=D,K<=106)
输出描述:
对于每次询问x,k输出以x为根的子树上，所有与x距离大于等于k的点与x的距离之和。(若不存在这样的点，则输出应为0)
示例1
输入

3
1 2
1 3
2
1 3
1 2
输出

3
5

题目链接：Wannafly挑战赛4 D
一开始感觉很像CF最近的某道题，然后按照那个思路预处理出每一个节点为根的子树下的所有距离及其前缀和，然后在线二分地回答，然而无限MLE……，后来看了别人的代码发现是我想多了，重新想了下题目的意思，实际上就是叫你求DFS序后某一个节点对应区间内大于等于询某长度的值那些数的和，显然只要对所有节点按照到树根的距离排序从大到小排序，对询问也按询问距离从大到小排序，然后离线做一遍树状数组更新答案即可，当然它询问的值需要变一下，比如询问的二元组是${u,k}$，也就是说某一个点到$u$的距离大于等于$k$，这样显然不太好求，由于是一棵树，两点之间路径唯一，因此我们要求的是这颗$u$的子树中的点到根节点的距离大于等于$dis[u]+k$的那些点。写到凌晨各种WA，早上起来重写一遍就AC了……神奇……
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define CLR(arr,val) memset(arr,val,sizeof(arr))
typedef long long LL;
const int N = 2e5 + 7;
int n, q;
struct edge
{
    int to, nxt;
    LL d;
    edge() {}
    edge(int _to, int _nxt, LL _d): to(_to), nxt(_nxt), d(_d) {}
} E[N];
struct bit
{
    LL T[N];
    void add(int k, LL v)
    {
        while (k <= n)
        {
            T[k] += v;
            k += (k & -k);
        }
    }
    LL sum(int k)
    {
        LL ret = 0;
        while (k)
        {
            ret += T[k];
            k -= (k & -k);
        }
        return ret;
    }
    LL query(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
} Dis, Man;
int head[N], tot;
int L[N], R[N], ts;
LL dis[N], ans[N];
pair<LL, int>arr[N];
pair<LL, pair<int, int> >Q[N];

void init()
{
    CLR(head, -1);
    tot = 0;
    CLR(vis, false);
}
void dfs(int u, LL d)
{
    dis[u] = d;
    L[u] = ++ts;
    arr[u].fi = d;
    arr[u].se = u;
    for (int i = head[u]; ~i; i = E[i].nxt)
    {
        int v = E[i].to;
        dfs(v, d + E[i].d);
    }
    R[u] = ts;
}
inline void add(int s, int t, LL d)
{
    E[tot] = edge(t, head[s], d);
    head[s] = tot++;
}
int main(void)
{
    int i;
    init();
    scanf("%d", &n);
    for (i = 1; i < n; ++i)
    {
        int p;
        LL d;
        scanf("%d%lld", &p, &d);
        add(p, i + 1, d);
    }
    dfs(1, 0LL);
    sort(arr + 1, arr + 1 + n, [](const pair<LL, int> &a, const pair<LL, int> &b){return a.fi > b.fi;});
    scanf("%d", &q);
    for (i = 0; i < q; ++i)
    {
        scanf("%d%lld", &Q[i].se.fi, &Q[i].fi);
        Q[i].fi += dis[Q[i].se.fi];
        Q[i].se.se = i;
    }
    sort(Q, Q + q, [](const pair<LL, pair<int, int> > &a, const pair<LL, pair<int, int> > &b){return a.fi > b.fi;});
    int cur = 1;
    for (i = 0; i < q; ++i)
    {
        while (cur <= n && arr[cur].fi >= Q[i].fi)
        {
            int pos = arr[cur].se;
            Dis.add(L[pos], arr[cur].fi);
            Man.add(L[pos], 1LL);
            ++cur;
        }
        ans[Q[i].se.se] = Dis.query(L[Q[i].se.fi], R[Q[i].se.fi]) - dis[Q[i].se.fi] * Man.query(L[Q[i].se.fi], R[Q[i].se.fi]);
    }
    for (i = 0; i < q; ++i)
        printf("%lld\n", ans[i]);
    return 0;
}