正題

題目鏈接:https://www.luogu.com.cn/problem/P3899

---

題目大意

給出$n$個點的一棵有根樹，每次詢問一個$(p,k)$，求有多少個點對$(b,c)$滿足

$p$和$b$是$c$的祖先

$b$與$p$的距離不超過$k$
$$蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤$$

---

解題思路

首先如果$b$在$a$上方，那么點$b$的個數(shù)可以用深度來求，而$c$的數(shù)量就是$a$的子樹大小$?1$

如果$b$在$a$的下方，$c$的數(shù)量就是$b$的子樹大小$?1$，也就是對于每個$b$它的貢獻(xiàn)是它的子樹大小$?1$，那么就求我們在$a$的子樹中與$a$距離不超過$k$的點的權(quán)值和即可。

這個可以用$dfs$序和主席樹維護(hù)，時間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define siz(x) (ed[x]-dfn[x]+1) using namespace std; const ll N=3e5+10,M=6e6+10; struct node{ll to,next; }a[N*2]; ll n,q,tot,cnt,D,ls[N],dep[N]; ll dfn[N],ed[N],rt[N],rfn[N]; void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dfs(ll x,ll fa){dfn[x]=++cnt;rfn[cnt]=x;dep[x]=dep[fa]+1;D=max(D,dep[x]);for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;dfs(y,x);}ed[x]=cnt; } struct Seg_Tree{ll cnt,sum[M],ls[M],rs[M];ll Change(ll x,ll L,ll R,ll pos,ll val){ll y=++cnt;sum[y]=sum[x]+val;if(L==R){return y;}ll mid=(L+R)>>1;if(pos<=mid)ls[y]=Change(ls[x],L,mid,pos,val),rs[y]=rs[x];else rs[y]=Change(rs[x],mid+1,R,pos,val),ls[y]=ls[x];return y;}ll Ask(ll x,ll y,ll L,ll R,ll l,ll r){if(!(sum[y]-sum[x]))return 0;if(L==l&&R==r)return sum[y]-sum[x];ll mid=(L+R)>>1;if(r<=mid)return Ask(ls[x],ls[y],L,mid,l,r);if(l>mid)return Ask(rs[x],rs[y],mid+1,R,l,r);return Ask(ls[x],ls[y],L,mid,l,mid)+Ask(rs[x],rs[y],mid+1,R,mid+1,r);} }T; int main() {scanf("%lld%lld",&n,&q);for(ll i=1;i<n;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y);addl(y,x);}dfs(1,0);for(ll i=1;i<=n;i++){int x=rfn[i];rt[i]=T.Change(rt[i-1],1,D,dep[x],siz(x)-1);}while(q--){ll p,k;scanf("%lld%lld",&p,&k);ll ans=min(k,dep[p]-1)*(siz(p)-1);printf("%lld\n",ans+T.Ask(rt[dfn[p]],rt[ed[p]],1,D,dep[p]+1,dep[p]+k));} } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的P3899-[湖南集训]谈笑风生【主席树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。