P3899 [湖南集训]谈笑风生

你们搞的这道题啊，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)$ ，于是每次查询区间求和即可。

代码：

#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));
    }
}