★★★★ 输入文件：laugh.in 输出文件：laugh.out 简单对比
时间限制：3 s 内存限制：512 MB
【问题描述】
设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 行，每行对应一个询问，代表询问的答案。
laugh.in
5 3
1 2
1 3
2 4
4 5
2 2
4 1
2 3
laugh.out
3
1
3
数据范围 n<=300,000吧
主席树+dfs序
从要求看来，可以划分成两种情况：
1.b比a高明且a和b谈笑风生，那么c只需在a的子树中取就好了,此时贡献为size[p]*min(dep[p-1],k)
2.a比b高明且a和b谈笑风生，c在b的子树上，考虑到子树问题，想到dfs序，那么问题变为求子树a区间中深度在deep[p]+1~deep[p]+k中所有点size的和 ，这可以用主席树完成
#include <ctype.h> #include <vector> #include <cstdio> #define N 305000 typedef long long LL; using std::vector; struct cmt { int l,r; LL Size; }tr[N*20]; inline void Read(int &x) { register char ch=getchar(); for(x=0;!isdigit(ch);ch=getchar()); for(;isdigit(ch);x=x*10+ch-'0',ch=getchar()); } LL ans; int min(int a,int b) {return a>b?b:a;} int max(int a,int b) {return a>b?a:b;} vector<int>edge[N]; int t[N],dfn[N],l[N],r[N],n,q,dep[N],tim,siz[N],tot; void dfs(int x,int fa) { l[x]=++tim; dfn[tim]=x; dep[x]=dep[fa]+1; siz[x]=0; for(int i=0;i<edge[x].size();++i) { int v=edge[x][i]; if(v!=fa) { dfs(v,x); siz[x]+=siz[v]+1; } } r[x]=tim; } void update(int l,int r,int x,int &y,int a,int b) { y=++tot; tr[y].Size=tr[x].Size+b; if(l==r) return; tr[y].l=tr[x].l; tr[y].r=tr[x].r; int mid=(l+r)>>1; if(a<=mid) update(l,mid,tr[x].l,tr[y].l,a,b); else update(mid+1,r,tr[x].r,tr[y].r,a,b); } LL ask(int l,int r,int x,int y,int a,int b) { if(l==a&&r==b) return tr[y].Size-tr[x].Size; int mid=(l+r)>>1; if(a>mid) return ask(mid+1,r,tr[x].r,tr[y].r,a,b); else if(b<=mid) return ask(l,mid,tr[x].l,tr[y].l,a,b); else return ask(l,mid,tr[x].l,tr[y].l,a,mid)+ask(mid+1,r,tr[x].r,tr[y].r,mid+1,b); } int main(int argc,char *argv[]) { freopen("laugh.in","r",stdin); freopen("laugh.out","w",stdout); Read(n); Read(q); for(int u,v,i=1;i<n;++i) { Read(u); Read(v); edge[u].push_back(v); edge[v].push_back(u); } dfs(1,1); for(int i=1;i<=n;++i) update(1,n,t[i-1],t[i],dep[dfn[i]],siz[dfn[i]]); for(int p,k;q--;) { Read(p); Read(k); ans=0; ans=(LL)siz[p]*min(dep[p]-1,k); if(dep[p]!=n) ans+=ask(1,n,t[l[p]-1],t[r[p]],dep[p]+1,min(n,dep[p]+k)); printf("%lld ",ans); } return 0; }