wordpress 教育培训,网站seo服务公司,大型门户网站开发费用,查询网站备案显示划横线正题
题目链接: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));}
}
