网站托管多少钱,百度一下你就知道了百度,wordpress媒体库,wordpress 浏览器兼容正题
题目链接:https://www.luogu.com.cn/problem/P3899 题目大意
给出nnn个点的一棵有根树#xff0c;每次询问一个(p,k)(p,k)(p,k)#xff0c;求有多少个点对(b,c)(b,c)(b,c)满足 ppp和bbb是ccc的祖先bbb与ppp的距离不超过kkk 蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤…正题
题目链接:https://www.luogu.com.cn/problem/P3899 题目大意
给出nnn个点的一棵有根树每次询问一个(p,k)(p,k)(p,k)求有多少个点对(b,c)(b,c)(b,c)满足
ppp和bbb是ccc的祖先bbb与ppp的距离不超过kkk 蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤\color{white}蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤 解题思路
首先如果bbb在aaa上方那么点bbb的个数可以用深度来求而ccc的数量就是aaa的子树大小−1-1−1
如果bbb在aaa的下方ccc的数量就是bbb的子树大小−1-1−1也就是对于每个bbb它的贡献是它的子树大小−1-1−1那么就求我们在aaa的子树中与aaa距离不超过kkk的点的权值和即可。
这个可以用dfsdfsdfs序和主席树维护时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
#define siz(x) (ed[x]-dfn[x]1)
using namespace std;
const ll N3e510,M6e610;
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].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs(ll x,ll fa){dfn[x]cnt;rfn[cnt]x;dep[x]dep[fa]1;Dmax(D,dep[x]);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)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 ycnt;sum[y]sum[x]val;if(LR){return y;}ll mid(LR)1;if(posmid)ls[y]Change(ls[x],L,mid,pos,val),rs[y]rs[x];else rs[y]Change(rs[x],mid1,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(LlRr)return sum[y]-sum[x];ll mid(LR)1;if(rmid)return Ask(ls[x],ls[y],L,mid,l,r);if(lmid)return Ask(rs[x],rs[y],mid1,R,l,r);return Ask(ls[x],ls[y],L,mid,l,mid)Ask(rs[x],rs[y],mid1,R,mid1,r);}
}T;
int main()
{scanf(%lld%lld,n,q);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}dfs(1,0);for(ll i1;in;i){int xrfn[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 ansmin(k,dep[p]-1)*(siz(p)-1);printf(%lld\n,ansT.Ask(rt[dfn[p]],rt[ed[p]],1,D,dep[p]1,dep[p]k));}
}
