树的距离(DFS序离线)

题目描述

传送门:Wannafly挑战赛4

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 ≤ 2\times 10 ^ 5$,$1 ≤ D, K ≤ 10^6$)

输出描述

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

样例输入

1
2
3
4
5
6
3
1 2
1 3
2
1 3
1 2

样例输出

1
2
3
5

思路

  • 对于子树查询问题,我们考虑求出这些点的dfs序。这样一棵子树$x$就对应一个区间$[l[x], r[x]]$。
  • 由于我们查询点的满足$dis[i] ≥ dis[x] + k$,其中$dis[x]$表示根到结点$x$的距离。所以我们可以考虑将查询离线,按$dis[x] + k$降序排序后依次处理。
  • 对于每个查询,我们只需要将有用的点一点点加入树状数组(或线段树)(用一个优先队列维护),维护它们与根的距离以及出现的次数,那么这个查询的答案就是$$\sum_{i = l[x]} ^ {r[x]} dis[c[i]] - dis[x] * \sum_{i = l[x]} ^ {r[x]} count[i] $$
    其中$c[i]$表示dfs序中第$i$个位置的结点在原树中的编号,$count[i]$表示第$i$个位置的点是否被纳入了考虑。

PS:若要强制在线,可以使用可持久化数据结构。

代码

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
111
112
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int N = 2e5 + 5;
vector<PII> G[N];
int L[N], R[N], c[N], dfn;
ll cnt[N], dist[N], d[N];

inline void add(int pos, ll val, ll* T)
{
for (int i = pos; i < N; i += i & -i)
T[i] += val;
}

inline ll sum(int pos, ll* T)
{
ll ret = 0;
for (int i = pos; i; i -= i & -i)
ret += T[i];
return ret;
}

void dfs(int u)
{
L[u] = ++dfn;
c[L[u]] = u;
for (auto e : G[u])
{
int v = e.X, w = e.Y;
d[v] = d[u] + w;
dfs(v);
}
R[u] = dfn;
}

const int M = 1e6 + 5;

struct query
{
int x, k, id;
query() {}
query(int _x, int _k, int _id) : x(_x), k(_k), id(_id) {}
} Q[M];

typedef pair<ll, int> Node;
ll ans[M];

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n;
scanf("%d", &n);
for (int i = 2; i <= n; i++)
{
static int p, w;
scanf("%d%d", &p, &w);
G[p].pb(mp(i, w));
}
dfs(1);
int q;
scanf("%d", &q);
for (int i = 0; i < q; i++)
{
static int x, k;
scanf("%d%d", &x, &k);
Q[i] = query(x, k, i);
}
priority_queue<Node> que;
for (int i = 1; i <= n; i++) que.push(mp(d[i], i));
sort(Q, Q + q, [](query a, query b) {
return d[a.x] + a.k > d[b.x] + b.k;
});
for (int i = 0; i < q; i++)
{
int x = Q[i].x, k = Q[i].k, id = Q[i].id;
if (!que.empty())
{
Node tmp = que.top();
while (tmp.X >= d[x] + k)
{
int pos = tmp.Y;
que.pop();
add(L[pos], d[pos], dist);
add(L[pos], 1, cnt);
if (que.empty()) break;
tmp = que.top();
}
}
ans[id] = sum(R[x], dist) - sum(L[x], dist) -(sum(R[x], cnt) - sum(L[x], cnt)) * d[x];
}
for (int i = 0; i < q; i++)
printf("%lld\n", ans[i]);
return 0;
}
捐助作者