Steven_MengのBlog

传送门

你们搞的这道题啊,exciting。

首先,看到标题我们就知道用什么算法实现,于是我们使用主席树。

容易发现,$a,b$和$c$都在同一条到根节点的链上面,而且$c$是这条链最下面的节点,但是$a,b$关系未知。

于是分类讨论:

$1.b \in anc(a)$,发现$c \in subtree(a),dis(a,b) \le k$,发现$c$有$sz[a]-1$种选择,$b$有$\min(k,dep[a]-1)$,这里$dep[rt]=1$

于是乘法原理相乘即可。

1
(sz[u]-1)*min(k,dep[u]-1)

$2.a \in anc(b)$,这种情况比较复杂,

注意到$dis(a,b) \le k$,所以$b$能够选择的区域类似于红色区域。

选择好$b$以后,发现$c \in subtree(b)$于是每选择一个$b$会对答案产生$sz[b]-1$的贡献。

于是答案即是$\sum _{u ,dep[u] \in [dep[a],dep[a]+k]}(sz[u]-1)$

考虑每个节点开一棵主席树,对于下标为$d$的位置,维护$\sum _{u,dep[u]=d} (sz[u]-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
#include <bits/stdc++.h>
#define MAXN 300005
#define LOG 55
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int rt[MAXN];
namespace SegmentTree{
struct node{
int l,r;
int val;
}tree[MAXN*LOG];
#define lc(i) tree[i].l
#define rc(i) tree[i].r
inline void pushup(int i,int lson,int rson){
tree[i].val=tree[lson].val+tree[rson].val;
}
int tot;
void Update(int &i,int l,int r,int index,int val){
if (!i) i=++tot;
if (l==r) return tree[i].val+=val,void();
int mid=(l+r)>>1;
if (index<=mid) Update(lc(i),l,mid,index,val);
else Update(rc(i),mid+1,r,index,val);
pushup(i,lc(i),rc(i));
}
int Query(int i,int l,int r,int L,int R){
if (!i) return 0;
if (L<=l&&r<=R) return tree[i].val;
int mid=(l+r)>>1,ans=0;
if (L<=mid) ans+=Query(lc(i),l,mid,L,R);
if (mid<R) ans+=Query(rc(i),mid+1,r,L,R);
return ans;
}
void Merge(int &rt,int x,int y){//注意Merge要新建节点
if (!x||!y) return rt=x+y,void();
pushup(rt=++tot,x,y);
Merge(lc(rt),lc(x),lc(y));
Merge(rc(rt),rc(x),rc(y));
}
}
using namespace SegmentTree;
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
G[u].push_back(v);
}
int sz[MAXN],dep[MAXN],n,q;
void dfs(int u,int father){
dep[u]=dep[father]+1;
sz[u]=1;
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v!=father) {
dfs(v,u);
sz[u]+=sz[v];
}
}
Update(rt[u],1,n,dep[u],sz[u]-1);
if (father) Merge(rt[father],rt[father],rt[u]);
}
#undef int
int main(){
#define int long long
n=read(),q=read();
for (register int i=1;i<n;++i){
int u=read(),v=read();
AddEdge(u,v);
AddEdge(v,u);
}
dfs(1,0);
while (q--){
int u=read(),k=read();
printf("%lld\n",Query(rt[u],1,n,dep[u]+1,dep[u]+k)+(sz[u]-1)*min(k,dep[u]-1));
}
}

 评论