【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;
}

#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;

}

XG Zepto's

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

BZOJ原题地址

洛谷原题地址

思路

代码

Like this:

Related

BZOJ原题地址

洛谷原题地址

思路

代码

Share this:

Like this:

Related