BZOJ3653 谈笑风生

题面

$\text{BZOJ}$权限题

洛谷

题解

好久以前写的了,懒得写题解了

直接把yyb的蒯下来

首先根据题目给的条件,发现$a,b$都要是$c$的父亲。

所以这三个点是树上的一条深度单增的链。

因为$a,b$之间距离不超过$k$,并且$a$被钦定了,所以只有两种情况:

一种是$a$是$b$的祖先,贡献是$\sum_bsize[b]−1$,也就是所有$b$可以选择的点的子树和。

另外一种$b$是$a$的祖先,贡献是$\sum_bsize[a]−1$,钦定一个$b$之后,$c$可以在$a$的子树中任选。

第二种情况很简单,因为$size[a]$是定值,并且每个点的父亲是唯一的,所以第二部分很容易算。

困难的是第一部分,然而依旧不难吧。。。

方法很多,比如说,你把$dfs$序和深度看成$x,y$轴,这样子就是二维数点,直接主席树。

或者说直接点分治也可以。

当然,既然想写长链剖分,那就当然要用长链剖分来做啊。

我们发现,所有的值都由重儿子向后挪动一位得来,而我们要求的东西需要维护一个区间和。

这样子很不好用前缀和来做,所以我们可以用一个后缀和啊!

这样子就很舒服了,直接维护后缀和,然后长链剖分转移,可以做到复杂度$\text{O}(n)$。

代码

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
#include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;

inline int read()
{
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data*w;
}

const int maxn(300010);
struct node { int id, k; };
vector<node> q[maxn];
struct edge { int next, to; } e[maxn << 1];
int head[maxn], e_num, Dep[maxn], dep[maxn], fa[maxn], heavy[maxn], n, Q, size[maxn];
inline void add_edge(int from, int to) { e[++e_num] = {head[from], to}; head[from] = e_num; }
long long pool[maxn], *s[maxn], *pos = pool, ans[maxn];

void dfs(int x)
{
Dep[x] = dep[x] = dep[fa[x]] + 1; size[x] = 1;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == fa[x]) continue;
fa[to] = x; dfs(to); size[x] += size[to];
if(Dep[heavy[x]] < Dep[to]) heavy[x] = to;
}
if(heavy[x]) Dep[x] = Dep[heavy[x]];
}

void Solve(int x)
{
s[x][0] = size[x] - 1;
if(!heavy[x]) return;
s[heavy[x]] = s[x] + 1;
Solve(heavy[x]); s[x][0] += s[heavy[x]][0];
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == fa[x] || to == heavy[x]) continue;
s[to] = pos; pos += Dep[to] - dep[to] + 1; Solve(to);
for(RG int j = 0; j <= Dep[to] - dep[to]; j++) s[x][j + 1] += s[to][j];
s[x][0] += s[to][0];
}

for(RG vector<node>::iterator it = q[x].begin(); it != q[x].end(); ++it)
{
int id = it -> id, k = it -> k;
ans[id] += 1ll * (size[x] - 1) * min(dep[x] - 1, k);
if(k >= Dep[x] - dep[x]) ans[id] += s[x][0] - size[x] + 1;
else ans[id] += s[x][0] - size[x] - s[x][k + 1] + 1;
}
}

int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
n = read(); Q = read();
for(RG int i = 1, a, b; i < n; i++)
a = read(), b = read(), add_edge(a, b), add_edge(b, a);
dfs(1);
for(RG int i = 1, a, b; i <= Q; i++)
a = read(), b = read(), q[a].push_back({i, b});
s[1] = pos; pos += Dep[1]; Solve(1);
for(RG int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×