既然题目的名字是谈笑风生主图当然也要是谈笑风生啦QwQ
BZOJ原题地址
洛谷原题地址
思路
求位于同一条链上的三个点,使前两个点之间的距离小于等于k。
对于给定的 a 和 k,当 b 在 a 上方,显然答案是min(depth[a]-1,k)*(siz[a]-1)
;当 b 在 a 的下方,显然是求 a 的子树的前 k 层的每个节点的子树大小(不含其本身)之和。
可以用 DFS 序建主席树维护一定深度下子树大小之和。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#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; } |
主席题用主席树233