Ralph And His Tour in Binary Country(思维+乱搞)

描述

传送门:Codeforces - 894D

Ralph is in the Binary Country. The Binary Country consists of $n$ cities and $(n - 1)$ bidirectional roads connecting the cities. The roads are numbered from $1$ to $(n - 1)$, the $i$-th road connects the city labeled $⌊\frac{(i + 1)}{2}⌋$ (here $⌊x⌋$ denotes the $x$ rounded down to the nearest integer) and the city labeled $(i + 1)$, and the length of the $i$-th road is $L_i$.

Now Ralph gives you $m$ queries. In each query he tells you some city $A_i$ and an integer $H_i$. He wants to make some tours starting from this city. He can choose any city in the Binary Country (including $A_i$) as the terminal city for a tour. He gains happiness ($H_i - L$) during a tour, where $L$ is the distance between the city $A_i$ and the terminal city.

Ralph is interested in tours from $A_i$ in which he can gain positive happiness. For each query, compute the sum of happiness gains for all such tours.

Ralph will never take the same tour twice or more (in one query), he will never pass the same city twice or more in one tour.

Input

The first line contains two integers $n$ and $m$ ($1 ≤ n ≤ 10^6, 1 ≤ m ≤ 10^5$).

$(n - 1)$ lines follow, each line contains one integer $L_i$ ($1 ≤ L_i ≤ 10^5$), which denotes the length of the $i$-th road.

m lines follow, each line contains two integers $A_i$ and $H_i$ ($1 ≤ A_i ≤ n$, $0 ≤ H_i ≤ 10^7$).

Output

Print $m$ lines, on the $i$-th line print one integer — the answer for the $i$-th query.

Examples

  • input
1
2
3
4
2 2
5
1 8
2 4
  • output
1
2
11
4
  • input
1
2
3
4
5
6
7
8
9
10
6 4
2
1
1
3
2
2 4
1 3
3 2
1 7
  • output
1
2
3
4
11
6
3
28

Note

Here is the explanation for the second sample.

Ralph’s first query is to start tours from city $2$ and $H_i$ equals to $4$. Here are the options:

  • He can choose city $5$ as his terminal city. Since the distance between city $5$ and city $2$ is $3$, he can gain happiness $4 - 3 = 1$.
  • He can choose city $4$ as his terminal city and gain happiness $3$.
  • He can choose city $1$ as his terminal city and gain happiness $2$.
  • He can choose city $3$ as his terminal city and gain happiness $1$.
  • Note that Ralph can choose city $2$ as his terminal city and gain happiness $4$.
  • Ralph won’t choose city $6$ as his terminal city because the distance between city $6$ and city $2$ is $5$, which leads to negative happiness for Ralph.

So the answer for the first query is $1 + 3 + 2 + 1 + 4 = 11$.

思路

  • 首先预处理每个点到它子树各结点的距离并排序,这个可以dfs完成。在排序的时候,可以利用归并排序的思想,将左右子树已经排好序的有序集合进行合并。这样就不需要使用std::sort进行排序。时间复杂度为$O(n\log n)$。
  • 处理查询的时候,由于之前的预处理,计算当前点即可知道从当前点到它子树作为终点时对答案的贡献:这个过程只需要在预处理出的有序数组中二分得到能到达的位置即可;然后统计它的兄弟结点,接着向上统计至根结点即可。时间复杂度为$O(m\log^2n)$。具体实现细节见代码orz

代码

1
2
#define lson rt << 1
#define rson rt << 1 | 1
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
#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 = 2e6 + 5;
vector<ll> G[N];
vector<ll> pre[N];
int d[N];

void dfs(int rt, const int& n)
{
if (rt > n) return;
dfs(lson, n);
dfs(rson, n);
int pl = 0, pr = 0;
vector<ll>&A = G[lson], &B = G[rson], &C = G[rt];
int a = d[lson], b = d[rson];
int sl = A.size(), sr = B.size();
C.pb(0);
while (pl < sl && pr < sr)
{
if (A[pl] + a < B[pr] + b)
C.pb(A[pl++] + a);
else
C.pb(B[pr++] + b);
}
while (pl < sl) C.pb(A[pl++] + a);
while (pr < sr) C.pb(B[pr++] + b);
pre[rt].pb(0);
for (int i = 1; i < C.size(); i++)
pre[rt].pb(pre[rt][i - 1] + C[i]);
}

ll calc(int a, int h, const int& n)
{
if (h < 0 || a > n || a == 0) return 0;
int pos = upper_bound(G[a].begin(), G[a].end(), h) - G[a].begin() - 1;
if (~pos)
return (ll)h * (pos + 1) - pre[a][pos];
return 0;
}

ll solve(int a, int h, const int& n)
{
ll ans = 0;
ans += calc(a, h, n);
while (a > 1 && (h -= d[a]) > 0)
{
ans += h;
ans += calc(a ^ 1, h - d[a ^ 1], n);
a >>= 1;
}
return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, m;
while (~scanf("%d%d", &n, &m))
{
for (int i = 1; i <= n; i++)
G[i].clear(), pre[i].clear();
for (int i = 1; i < n; i++)
scanf("%d", &d[i + 1]);
dfs(1, n);
while (m--)
{
static int a, h;
scanf("%d%d", &a, &h);
printf("%lld\n", solve(a, h, n));
}
}
return 0;
}
捐助作者
0%