4
17
2016
0

[bzoj]3653: 谈笑风生

很久前看到的题,今天再来看发现似乎之前看错了题?

传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3653

之前可能没想到$b$是$a$的祖先这条潜在规则,然后以为是离线点分乱搞不会来

加上这条规则就变成傻题了


主要问题是求$a$的子树里距离$a$不超过$k$的点的子树大小和,主席树直接上就行了

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define N 300030
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
int i,j,k,m,mx,n,q,x,y,p,now,dep[N],in[N],sz[N],ot[N],cnt,last[N],rk[N],L,R,V;
struct edge{int to,next;}e[N<<1];
struct tree{tree*l,*r;ll s;}C[N*20],*c=C+1,*T[N],*null=C;
inline void add(int u,int v){
	e[++cnt]=(edge){v,last[u]},last[u]=cnt;
	e[++cnt]=(edge){u,last[v]},last[v]=cnt;
}
#define max(a,b) ((a)>(b)?(a):(b))
void dfs(int x,int fa){
	mx=max(mx,dep[x]),rk[in[x]=++now]=x;
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa)dep[y]=dep[x]+1,dfs(y,x),sz[x]+=sz[y]+1;ot[x]=now;
}
#define ls o->l,l,m
#define rs o->r,m+1,r
void insert(tree*&o,int l,int r,int k){
	o==0?o=++c:o=&(*(++c)=*o);o->s+=V;
	int m=l+r>>1;if(l^r)k<=m?insert(ls,k):insert(rs,k);
}
#define min(a,b) ((a)<(b)?(a):(b))
ll ask(tree*o,int l,int r){
	if(o==NULL)return 0;if(l>=L&&r<=R)return o->s;
	int m=l+r>>1;ll ans=0;if(L<=m)ans=ask(ls);if(R>m)ans+=ask(rs);return ans;
}
int main(){
	for(n=read(),q=read(),i=1;i<n;++i)add(read(),read());
	for(dfs(1,0),T[(i=1)-1]=++c;i<=n;++i)V=sz[rk[i]],insert(T[i]=T[i-1],0,mx,dep[rk[i]]);
	while(q--)p=read(),k=read(),L=dep[p]+1,R=min(mx,dep[p]+k),printf("%lld\n",1ll*min(dep[p],k)*sz[p]+ask(T[ot[p]],0,mx)-ask(T[in[p]],0,mx));
}

 

$loading...$

Category: bzoj | Tags: DFS序 主席树 | Read Count: 596

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com