【BZOJ 3653】【湖南集训】谈笑风生 / 题解

【BZOJ 3653】【湖南集训】谈笑风生 / 题解

既然题目的名字是谈笑风生主图当然也要是谈笑风生啦QwQ

BZOJ原题地址

洛谷原题地址

思路

求位于同一条链上的三个点,使前两个点之间的距离小于等于k。

对于给定的 a 和 k,当 b 在 a 上方,显然答案是min(depth[a]-1,k)*(siz[a]-1);当 b 在 a 的下方,显然是求 a 的子树的前 k 层的每个节点的子树大小(不含其本身)之和。
可以用 DFS 序建主席树维护一定深度下子树大小之和。

代码

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define maxn 300010
#define ll long long
using namespace std;
int read(){
	int x=0,flag=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if (ch=='-') flag=-1,ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
	return x*flag;
}
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
}l[maxn*2];
int head[maxn],ind,cnt,n,q,t1,t2;
int dfn[maxn][2],id[maxn];
int rt[maxn],ls[maxn<<7],rs[maxn<<7];
ll t[maxn<<7],d[maxn],siz[maxn];
void Add(int a,int b){
    l[++cnt]=Edge(b,head[a]);
    head[a]=cnt;
}
void Dfs(int u,int f){
    d[u]=d[f]+1;siz[u]=1;
    dfn[u][0]=++ind;id[ind]=u;
    for (int i=head[u];i;i=l[i].next){
        int v=l[i].to;if (v==f) continue;
        Dfs(v,u);siz[u]+=siz[v];
    }
    dfn[u][1]=ind;
}
void Update(int &p,int pre,int l,int r,int x,int v){
	p=++cnt;t[p]=t[pre]+v;
	if (l==r) return;
	if (mid>=x) rs[p]=rs[pre],Update(ls[p],ls[pre],l,mid,x,v);
	else ls[p]=ls[pre],Update(rs[p],rs[pre],mid+1,r,x,v);
}
ll Query(int p,int l,int r,int L,int R){
	if (L<=l&&r<=R) return t[p];
	if (mid>=R) return Query(ls[p],l,mid,L,R);
	if (mid<L) return Query(rs[p],mid+1,r,L,R);
	return Query(ls[p],l,mid,L,R)+Query(rs[p],mid+1,r,L,R);
}
ll Solve(int x,int y){
	ll res=min(d[x]-1,y)*(siz[x]-1);
	int l=dfn[x][0],r=dfn[x][1];
	ll tmp=Query(rt[r],1,n,d[x],d[x]+y)-
	Query(rt[l],1,n,d[x],d[x]+y);
	return res+tmp;
}
int main(){
    n=read(),q=read();
    for (int i=1;i<n;i++)
        t1=read(),t2=read(),
		Add(t1,t2),Add(t2,t1);
    Dfs(1,0);
    for (int i=1;i<=n;++i)
    	Update(rt[i],rt[i-1],1,n,d[id[i]],siz[id[i]]-1);
    for (int i=1;i<=q;i++){
        t1=read(),t2=read();
        printf("%lld\n",Solve(t1,t2));
    }
    return 0;
}
Show Comments