主席树板子了
首先看到这个暴力异常的题面, 感觉做了这道题的会没命的
首先先考虑 \(b\) 在 \(a\) 子树内部的情况, 这个样子的话我们需要知道子树内部所有深度小于等于 \(deep[a]+k\) 的点带来的贡献是是多少, 由于这里的 \(a,b,c\) 都不能是同一个节点, 所以这里的贡献就是子树大小减 1, 同时 \(b\) 也不能是 \(a\)
之后按照深度建主席树就好了, 权值是子树大小减 1, 我们就可以快速的查询点子树内部所有距离它的点小于等于 \(k\) 的点带来的权值和了
之后在考虑子树外部的情况, 由于 \(a,b\) 都是 \(c\) 的祖先, 所以 \(b\) 不在 \(a\) 子树内部的话就必定在 \(a\) 到根的路径上, 而 \(c\) 也只能在 \(a\) 的子树里选取, 所以权值是 \(sum[a]-1\), 至于 \(b\) 的选择我们就可以从 \(a\) 往上的 \(k\) 个节点
代码
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #define re register
- #define maxn 300005
- #define max(a,b) ((a)>(b)?(a):(b))
- #define min(a,b) ((a)<(b)?(a):(b))
- #define LL long long
- struct E
- {
- int v,nxt;
- }e[maxn<<1];
- int l[maxn*20],r[maxn*20];
- LL d[maxn*20];
- int cnt,tot;
- int build(int x,int y)
- {
- int root=++cnt;
- if(x==y) return root;
- int mid=x+y>>1;
- l[root]=build(x,mid);
- r[root]=build(mid+1,y);
- return root;
- }
- int change(int pre,int x,int y,int pos,LL val)
- {
- int root=++cnt;
- d[root]=d[pre]+val;
- if(x==y) return root;
- l[root]=l[pre],r[root]=r[pre];
- int mid=x+y>>1;
- if(pos<=mid) l[root]=change(l[pre],x,mid,pos,val);
- else r[root]=change(r[pre],mid+1,y,pos,val);
- return root;
- }
- LL query(int pos,int x,int y,int xx,int yy)
- {
- if(xx<=x&&yy>=y) return d[pos];
- int mid=x+y>>1;
- if(yy<=mid) return query(l[pos],x,mid,xx,yy);
- if(xx>mid) return query(r[pos],mid+1,y,xx,yy);
- return query(l[pos],x,mid,xx,yy)+query(r[pos],mid+1,y,xx,yy);
- }
- int head[maxn],deep[maxn],to[maxn],rt[maxn],_to[maxn];
- LL p[maxn],sum[maxn];
- int n,Q,num,maxdep;
- inline void add_edge(int x,int y)
- {
- e[++num].v=y;
- e[num].nxt=head[x];
- head[x]=num;
- }
- inline int read()
- {
- char c=getchar();
- int x=0;
- while(c<'0'||c>'9') c=getchar();
- while(c>='0'&&c<='9')
- x=(x<<3)+(x<<1)+c-48,c=getchar();
- return x;
- }
- void dfs(int x)
- {
- sum[x]=1;
- to[x]=++tot;
- _to[tot]=x;
- for(re int i=head[x];i;i=e[i].nxt)
- if(!deep[e[i].v])
- {
- deep[e[i].v]=deep[x]+1;
- p[e[i].v]=p[x]+1;
- dfs(e[i].v);
- sum[x]+=sum[e[i].v];
- }
- maxdep=max(maxdep,deep[x]);
- }
- int main()
- {
- n=read();Q=read();
- int x,y;
- for(re int i=1;i<n;i++)
- {
- x=read(),y=read();
- add_edge(x,y),add_edge(y,x);
- }
- deep[1]=1;
- dfs(1);
- rt[0]=build(1,maxdep);
- for(re int i=1;i<=n;i++)
- rt[i]=change(rt[i-1],1,maxdep,deep[_to[i]],sum[_to[i]]-1);
- LL k;
- while(Q--)
- {
- x=read(),k=read();
- LL ans=0;
- ans=min(p[x],k)*(sum[x]-1);
- y=to[x]+sum[x]-1;
- if(deep[x]!=maxdep)
- ans+=query(rt[y],1,maxdep,deep[x]+1,min(deep[x]+k,maxdep))-query(rt[to[x]-1],1,maxdep,deep[x]+1,min(deep[x]+k,maxdep));
- printf("%lld",ans),putchar(10);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2905331.html