[湖南集训] 谈笑风生

题目描述

设 T 为一棵有根树，我们做如下的定义：

• 设 a 和 b 为 T 中的两个不同节点。如果 a 是 b 的祖先，那么称“a 比 b 不知道高明到哪里去了”。

• 设 a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定常数 x，那么称“a 与 b 谈笑风生”。

给定一棵 n 个节点的有根树 T，节点的编号为 1 ∼ n，根节点为 1 号节点。你需要回答 q 个询问，询问给定两个整数 p 和 k，问有多少个有序三元组 (a; b; c) 满足：

1. a、 b 和 c 为 T 中三个不同的点，且 a 为 p 号节点；

2. a 和 b 都比 c 不知道高明到哪里去了；

3. a 和 b 谈笑风生。这里谈笑风生中的常数为给定的 k。

输入输出格式

输入格式：

输入文件的第一行含有两个正整数 n 和 q，分别代表有根树的点数与询问的个数。

接下来 n − 1 行，每行描述一条树上的边。每行含有两个整数 u 和 v，代表在节点 u 和 v 之间有一条边。

接下来 q 行，每行描述一个操作。第 i 行含有两个整数，分别表示第 i 个询问的 p 和 k。

输出格式：

输出 q 行，每行对应一个询问，代表询问的答案。

输入输出样例

输入样例#1：

5 3

1 2

1 3

2 4

4 5

2 2

4 1

2 3

输出样例#1：

3

1

3

说明

样例中的树如下图所示：

对于第一个和第三个询问，合法的三元组有 (2,1,4)、 (2,1,5) 和 (2,4,5)。

对于第二个询问，合法的三元组只有 (4,2,5)。

所有测试点的数据规模如下：

对于全部测试数据的所有询问， 1 ≤ p ≤ n， 1 ≤ k ≤ n.

Solution

....(然而蒟蒻我并不会)

其实题目的信息可以概括为这么几个条件

1. a和b都是c的祖先节点2. a和b不是同一个节点3. a和b在树中的深度之差的绝对值不超过k

那么其实我们可以分类讨论一下,对于\(b\)在\(a\)的上面的情况,\(c\)只能是\(a\)的子树中的节点,又因为不能为\(a\),所以有\(size[a]-1\)种可能,而\(b\)既然在a的上方,那就只有\(min(k,dep[a]-1)\)种取值了

所以很明显,这一部分的\(ans=min(k,dep[a]-1)\times (size[a]-1)\)

那么如果\(b\)在\(a\)的下方,则\(c\)只能为\(b\)的子树节点,所以对于一个节点,它对答案的贡献显然为\(size[]-1\),我们把这个答案用前缀和记录下来,用一种类似差分的方法查询就行了

怎么搞?线段树啊,主席树啊随便你乱搞...反正我写的是主席树

主席树的话，因为我们要求贡献，那么肯定是要把\(size[]\)当权值插入了,那就只能把\(dfs\)序当下标建树了

查询的时候也像线段树那样查个差值就好了

然后两个部分的答案加起来就好了

注意1:如果当前点的深度已经是最大深度了，就代表不可能有节点c了，输出0

注意2:开 long long

Code

#include
    
     #define in(i) (i=read())#define il extern inline#define rg register#define mid ((l+r)>>1)#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))#define lol long longusing namespace std;const lol N=3e5+10;lol read() {    lol ans=0, f=1; char i=getchar();    while (i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}    while (i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+(i^48), i=getchar();    return ans*f;}lol n,m,cur,maxn,cnt,tot;lol head[N],nex[N<<1],to[N<<1];lol rt[N],dep[N],size[N],dfn[N];struct Chair_Tree {    lol l,r,v;}t[N<<5];void add(lol a,lol b) {    to[++cur]=b,nex[cur]=head[a],head[a]=cur;    to[++cur]=a,nex[cur]=head[b],head[b]=cur;}void insert(lol &u,lol l,lol r,lol pre,lol pos,lol v) {    t[u=++tot]=t[pre], t[u].v+=v;    if(l==r) return;    if(pos<=mid) insert(t[u].l,l,mid,t[pre].l,pos,v);    else insert(t[u].r,mid+1,r,t[pre].r,pos,v);}lol query(lol u,lol v,lol l,lol r,lol left,lol right,lol ans=0) {    //cout<
     
      <<" "<
      
       <<" "<
       
        <