[文章目录]
Description
设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。
b在a上面的随便搞。b在a下面的可以先树形DP，dp[i]表示a在i这个位置，b在a子树中不和a供点的方案数，那么对于距离限度为k，b的范围固定，差分dp值。在该深度通过dfs找到子树对应区间，减去dp值的前缀和即可。
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char ch=nc();
while(ch<'0'||ch>'9') ch=nc();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=nc();
}
int n,m,mx;
int head[301000],to[601000],nxt[601000],cnt;
ll dp[301000];
int siz[301000],in[301000],out[301000],dep[301000],tot;
vector<int>b[301000];
vector<ll>s[301000];
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
void dfs(int x,int pre)
{
dep[x]=dep[pre]+1; mx=max(mx,dep[x]);
in[x]=++tot; b[dep[x]].push_back(x);
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
{
dfs(to[i],x);
siz[x]+=siz[to[i]];
dp[x]+=dp[to[i]]+siz[to[i]]-1;
}
siz[x]++; out[x]=tot;
}
ll work(int x,int L,int R)
{
if(x>mx) return 0;
int l=0,r=(int)b[x].size(),mid;
ll re=0;
while(l<r)
{
mid=(l+r)>>1;
if(in[b[x][mid]]>=L) r=mid;
else l=mid+1;
}
if(r-1<(int)b[x].size()&&r-1>=0) re-=s[x][r-1];
l=0,r=(int)b[x].size();
while(l<r)
{
mid=(l+r)>>1;
if(in[b[x][mid]]<=R) l=mid+1;
else r=mid;
}
if(l-1<(int)b[x].size()&&l-1>=0) re+=s[x][l-1];
return re;
}
int main()
{
read(n); read(m);
int x,y;
for(int i=1;i!=n;++i)
{
read(x); read(y);
add(x,y);
}
dfs(1,0); ll sum;
for(int i=1;i<=mx;++i)
{
sum=0;
for(int j=0;j<(int)b[i].size();++j)
{
sum+=dp[b[i][j]];
s[i].push_back(sum);
}
}
ll ans,tmp; int p,k;
while(m--)
{
read(p); read(k);
ans=dp[p]; ans-=work(dep[p]+k,in[p],out[p]);
tmp=min(dep[p]-1,k);
if(tmp>=1) ans+=tmp*(siz[p]-1);
printf("%lld\n",ans);
}
return 0;
}