题意：
给一棵树，求三元组(a,b,c)满足a和b都是c的祖先，且b到a的距离小于等于k，a和k给定
题解：
分情况讨论(以下内容的子节点数都不包括自己本身)。
如果b是a的祖先，那么贡献就是(a的子节点数*(k和a的祖先的最小值))。很好理解，因为b是a的祖先且距离小于等于k，所以b不能超过a的k级父亲，但a不一定有k个父亲，所以取最小值。每一个b都可以取a的所有子节点。
如果b是a的儿子，那么对于任意一个合法的b，贡献为它的子节点数，因为c可以在它的子节点中任选。接下来问题就变成了：求一个节点的子节点中，到这个节点距离小于等于k的所有点的权值（即子节点数）之和。在子节点中，可以转化为dfs序上的一段区间。距离小于等于k，可以表示成深度在(dep[a]+1)~(dep[a]+k)之中，接着可以使用可持久化线段树维护。
#include<cstdio> #include<vector> #include<algorithm> #include<cstdlib> using namespace std; int n,q,cnt,rt[300002],dep[300002],zjds[300002],dfn[300002],df,t[300002]; vector<int>g[300002]; typedef struct{ long long sum; int ls,rs; }P; P p[10000002]; void dfs(int x,int y){ dep[x]=dep[y]+1;dfn[x]=++df;t[df]=x;zjds[x]=1; for (int i=0;i<g[x].size();i++) if (g[x][i]!=y) { dfs(g[x][i],x);zjds[x]+=zjds[g[x][i]]; } } void gengxin(int r1,int r2,int begin,int end,int wz,int z){ if (begin==end) { p[r2].sum=p[r1].sum+z; return; } int mid=(begin+end)/2; if (wz<=mid) { p[r2].ls=++cnt;p[r2].rs=p[r1].rs; gengxin(p[r1].ls,p[r2].ls,begin,mid,wz,z); } else { p[r2].rs=++cnt;p[r2].ls=p[r1].ls; gengxin(p[r1].rs,p[r2].rs,mid+1,end,wz,z); } p[r2].sum=p[p[r2].ls].sum+p[p[r2].rs].sum; } long long chaxun(int root,int begin,int end,int begin2,int end2){ if (begin>end2 || end<begin2 || !root)return 0; if (begin>=begin2 && end<=end2)return p[root].sum; int mid=(begin+end)/2; return chaxun(p[root].ls,begin,mid,begin2,end2)+chaxun(p[root].rs,mid+1,end,begin2,end2); } int main() { scanf("%d%d",&n,&q); for (int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); g[u].push_back(v);g[v].push_back(u); } dfs(1,0); for (int i=1;i<=n;i++) { rt[i]=++cnt; gengxin(rt[i-1],rt[i],1,n,dep[t[i]],zjds[t[i]]-1); } for (int i=1;i<=q;i++) { int a,k,t1,t2; scanf("%d%d",&a,&k); t1=dfn[a];t2=dfn[a]+zjds[a]-1; printf("%lld ",(long long)(zjds[a]-1)*min(k,dep[a]-1)+chaxun(rt[t2],1,n,dep[a]+1,dep[a]+k)-chaxun(rt[t1],1,n,dep[a]+1,dep[a]+k)); } return 0; }