正題

P3899

---

題目大意

給你一棵樹，對于每次詢問，給出x,k，問你有多少個(gè)三元組(y,z)滿足x,y,z不同，x,y之間的距離小于k，且x,y都是z的祖先

---

解題思路

若y的深度小于x，那么一定在x到根節(jié)點(diǎn)的路徑上，答案為 $min(de{p}_x?1,k)\times (s{z}_x?1)$

若y的深度大于x，那么可以以深度為下標(biāo)，dfs序?yàn)闀r(shí)間坐標(biāo)構(gòu)造主席樹，每次詢問直接在子樹的限定深度內(nèi)查詢即可

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 300300 using namespace std; ll n,q,x,y,w,tot,h[N],rt[N],sz[N],dfn[N],dep[N],low[N]; struct rec {ll to,nx; }e[N<<1]; void add(ll x,ll y) {e[++tot].to=y;e[tot].nx=h[x];h[x]=tot;return; } struct Tree {ll s[N<<5],ls[N<<5],rs[N<<5];void push_up(ll x){s[x]=s[ls[x]]+s[rs[x]];return;}ll change(ll lst,ll l,ll r,ll y,ll z){ll x=++w;if(l==r){s[x]=s[lst]+z;return x;}ll mid=l+r>>1;if(y<=mid)ls[x]=change(ls[lst],l,mid,y,z),rs[x]=rs[lst];else ls[x]=ls[lst],rs[x]=change(rs[lst],mid+1,r,y,z);push_up(x);return x;}ll ask(ll x,ll L,ll R,ll l,ll r){if(L==l&&R==r)return s[x];ll mid=L+R>>1;if(r<=mid)return ask(ls[x],L,mid,l,r);else if(l>mid)return ask(rs[x],mid+1,R,l,r);else return ask(ls[x],L,mid,l,mid)+ask(rs[x],mid+1,R,mid+1,r);} }T; void dfs1(ll x,ll fa) {dfn[x]=++w;sz[x]=1;for(ll i=h[x];i;i=e[i].nx){ll y=e[i].to;if(y==fa)continue;dep[y]=dep[x]+1;dfs1(y,x);sz[x]+=sz[y];}low[x]=w;return; } void dfs2(ll x,ll fa) {rt[dfn[x]]=T.change(rt[dfn[x]-1],1,n,dep[x],sz[x]-1);for(ll i=h[x];i;i=e[i].nx){ll y=e[i].to;if(y==fa)continue;dfs2(y,x);}return; } int main() {scanf("%lld%lld",&n,&q);for(ll i=1;i<n;++i){scanf("%lld%lld",&x,&y);add(x,y);add(y,x);}dep[1]=1;dfs1(1,0);dfs2(1,0);while(q--){scanf("%lld%lld",&x,&y);printf("%lld\n",min(dep[x]-1,y)*(sz[x]-1)+T.ask(rt[low[x]],1,n,min(dep[x]+1,n),min(dep[x]+y,n))-T.ask(rt[dfn[x]],1,n,min(dep[x]+1,n),min(dep[x]+y,n)));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【主席树】更为厉害（P3899）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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