【bzoj3653】【谈笑风生】【dfs序+主席树】

设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 行，每行对应一个询问，代表询问的答案。

1<=P<=N

1<=K<=N

N<=300000

Q<=300000

题解:

          首先询问1很好处理.

          对于询问2,对dfs序建主席树即可.每次询问就是查询p所在子树中,深度在[deep[p]+1,deep[p]+k]的节点的size和.

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#define LL long long
#define N 300010 
using namespace std;
int n,Q,k,p,x,y,point[N],next[N<<1],sz,cnt,num,mx,in[N],out[N],deep[N],q[N];
int root[N],ls[N*20],rs[N*20];
LL sum[N*20],ans,size[N];
struct use{int st,en;}e[N<<1];
void add(int x,int y){next[++cnt]=point[x];point[x]=cnt;e[cnt].en=y;}
int read(){int x=0;char ch=getchar();while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x;
}
void dfs(int x,int fa){in[x]=++num;q[num]=x;for(int i=point[x];i;i=next[i])if(e[i].en!=fa){deep[e[i].en]=deep[x]+1;mx=max(mx,deep[e[i].en]);dfs(e[i].en,x);size[x]+=size[e[i].en]+1;}out[x]=num;
}
void insert(int x,int &y,int l,int r,int p,LL v){y=++sz;sum[y]=sum[x]+v;if(l==r)return;ls[y]=ls[x];rs[y]=rs[x];int mid=(l+r)>>1;if(p<=mid)insert(ls[x],ls[y],l,mid,p,v);else insert(rs[x],rs[y],mid+1,r,p,v);
}
LL query(int x,int y,int l,int r,int ll,int rr){rr=min(rr,r);if (ll>rr) return 0;if(l==ll&&r==rr) return sum[y]-sum[x];int mid=(l+r)>>1;if(rr<=mid)return query(ls[x],ls[y],l,mid,ll,rr);else if(mid<ll)return query(rs[x],rs[y],mid+1,r,ll,rr);else return query(ls[x],ls[y],l,mid,ll,mid)+query(rs[x],rs[y],mid+1,r,mid+1,rr);
}
int main(){n=read();Q=read();for(int i=1;i<n;i++){x=read();y=read();add(x,y);add(y,x);}dfs(1,0);for(int i=1;i<=n;i++) insert(root[i-1],root[i],0,mx,deep[q[i]],size[q[i]]);for(int i=1;i<=Q;i++) {p=read();k=read();ans=0;ans+=size[p]*(LL)min(deep[p],k);ans+=query(root[in[p]-1],root[out[p]],0,mx,deep[p]+1,deep[p]+k);printf("%lld\n",ans);}
}