输出 q 行，每行对应一个询问，代表询问的答案。
Hint:边要加双向
___________________________________________________________
DFS序+离线分层处理数据
求书上符合条件的三元组（a,b,c）的数量。a为给定点，b点到a点的距离不超过一直量k，且a,b为祖孙的关系，c为a、b的子孙。
根据a、b的关系分成两类：
1、b为a的祖先。那么b的可能有min(k,dep[a]-1)种，而c的可能为siz[a]-1种，那么两个值的成绩就是答案。
2、b为a的子孙，那么b的可能为所有与a深度差不超过k的子孙点,而c点的肯为对应每个b点的子孙树（siz[b]-1）
第一种情况比较好求，深搜可以求出对应dep[]和siz[]，然后乘起来就好了
第二种情况比较麻烦，因为有多问，没问要遍历所有b的可能点，然后求对应c点的可能（siz[b]-1）之和。这个复杂度太高，不可完成。
所以离线，把所有问题保存起来，其中每一问b点的最深深度是关键，用它对问题进行重新排序。这样一层一层的更新每个点的子孙数量（-1），用树状数组维护，但已经更新到当前这一问的最深深度时，用树状数组求出对应子树的和，就是答案。
按照黄学长的说法，离线比较简单，但是我没有怎么学过离线的算法，所以理解了好一会儿，很巧妙！膜拜一下！
___________________________________________________________
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=3e5+10; 4 int n,m; 5 struct edge 6 { 7 int u,v,nxt; 8 }e[maxn<<1]; 9 int head[maxn],js; 10 void addage(int u,int v) 11 { 12 e[++js].u=u;e[js].v=v; 13 e[js].nxt=head[u];head[u]=js; 14 } 15 int dep[maxn],lt[maxn],rt[maxn],cnt,siz[maxn],depf[maxn]; 16 void dfs(int u,int fa) 17 { 18 dep[u]=dep[fa]+1; 19 lt[u]=++cnt; 20 siz[u]=1; 21 for(int i=head[u];i;i=e[i].nxt) 22 { 23 int v=e[i].v; 24 if(v==fa)continue; 25 dfs(v,u); 26 depf[u]=max(depf[u],depf[v]); 27 siz[u]+=siz[v]; 28 } 29 depf[u]++; 30 rt[u]=cnt; 31 } 32 int Q[maxn],t,h; 33 void bfs() 34 { 35 h=0; 36 Q[t=1]=1; 37 while(t>h) 38 { 39 int u=Q[++h]; 40 for(int i=head[u];i;i=e[i].nxt) 41 { 42 int v=e[i].v; 43 if(dep[v]<dep[u])continue; 44 Q[++t]=v; 45 } 46 } 47 } 48 struct que 49 { 50 int p,k,dp,id; 51 long long ans; 52 }q[maxn]; 53 bool cmp(que a,que b) 54 { 55 return a.dp<b.dp; 56 } 57 long long da[maxn]; 58 long long sz[maxn]; 59 void change(int x,int y) 60 { 61 for(int i=x;i<=n;i+=i&(-i))sz[i]+=y; 62 } 63 long long query(int x) 64 { 65 long long ans=0; 66 for(int i=x;i>0;i-=i&(-i))ans+=sz[i]; 67 return ans; 68 } 69 int main() 70 { 71 scanf("%d%d",&n,&m); 72 for(int u,v,i=1;i<n;++i) 73 { 74 scanf("%d%d",&u,&v); 75 addage(u,v);addage(v,u); 76 } 77 dfs(1,0); 78 bfs(); 79 for(int i=1;i<=m;++i) 80 { 81 scanf("%d%d",&q[i].p,&q[i].k); 82 q[i].dp=min(dep[q[i].p]+q[i].k,depf[q[i].p]+dep[q[i].p]-1); 83 q[i].id=i; 84 q[i].ans=1LL*min(dep[q[i].p]-1,q[i].k)*(siz[q[i].p]-1); 85 } 86 sort(q+1,q+1+m,cmp); 87 int cur=1; 88 for(int i=1;i<=m;++i) 89 { 90 int deep=q[i].dp; 91 while(Q[cur]!=0 && dep[Q[cur]]<=deep) 92 { 93 change(lt[Q[cur]],siz[Q[cur]]-1); 94 cur++; 95 } 96 q[i].ans+=query(rt[q[i].p])-query(lt[q[i].p]); 97 } 98 for(int i=1;i<=m;++i)da[q[i].id]=q[i].ans; 99 for(int i=1;i<=m;++i)printf("%lld\n",da[i]); 100 return 0; 101 }
原文：https://www.cnblogs.com/gryzy/p/11797330.html
