首页 > 其他分享 >题解 P5384

题解 P5384

时间:2023-07-17 22:00:22浏览次数:36  
标签:node ch val int 题解 dep P5384 id

这题有紫??

对于询问节点 \(u\),倍增地跳到它的 \(k\) 级祖先,求其子树内有多少深度为 \(dep_u\) 的节点。

我们考虑把询问离线,再通过 dfs 序把树拍平,然后扫一遍直接求就行了。

复杂度 \(O(n\log n)\)。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,q,ans[N],l[N],r[N],tot=0,a[N],dep[N],fa[N][22],cnt[N];
vector<int>adj[N];
struct node{
  int val,id,op;
  node(int val=0,int id=0,int op=0):val(val),id(id),op(op){}
};
vector<node>d[N];
void dfs(int u,int lst){
  l[u]=++tot;dep[u]=dep[lst]+1;a[tot]=dep[u];
  for(int i=1;i<=20;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
  for(int i=0;i<adj[u].size();++i)dfs(adj[u][i],u);
  r[u]=tot;
}
int main(){
  cin>>n>>q;
  for(int i=2;i<=n;++i){
    fa[i][0]=read();
    adj[fa[i][0]].push_back(i);
  }
  dfs(1,0);
  for(int i=1;i<=q;++i){
    int u,t,v;u=read();t=read();v=dep[u];
    for(int i=0;i<=20;++i)if((t>>i)&1)u=fa[u][i];
    d[l[u]-1].push_back(node(v,i,-1));
    d[r[u]].push_back(node(v,i,1));
  }
  for(int i=1;i<=n;++i){
    ++cnt[a[i]];
    for(int j=0;j<d[i].size();++j){
      node tmp=d[i][j];
      ans[tmp.id]+=tmp.op*cnt[tmp.val];
    }
  }
  for(int i=1;i<=q;++i)printf("%d ",max(ans[i]-1,0));
  cout<<endl;
  return 0;
}

标签:node,ch,val,int,题解,dep,P5384,id
From: https://www.cnblogs.com/HQJ2007/p/17561374.html

相关文章

  • 题解 P3806
    点分治模板题。点分治适合处理大规模的树上路径信息问题暴力做法:dfs每个点\(u\),算出其子树内每个点到\(u\)的距离,统计经过\(u\)的所有路径,复杂度\(O(n^2)\)。容易发现,复杂度和子树大小有关。对于当前子树,我们可以求出其重心,计算经过重心的所有路径,删掉重心,递归每个联通......
  • 题解 CF1271D
    贪心+DP。对于一个点,后选显然比先选好,也就是说每个点都对应了唯一一个来源。于是我们可以把每个点所能回溯到的点的收益值从大到小排序,贪心地选前缀。定义\(f_{i,j}\)表示考虑了前\(i\)个点,剩下\(j\)个人,最大收益。转移方程和\(01\)背包的一样。\[f_{i,j}=f_{i-1,j-b......
  • 题解 CF213C
    考虑朴素DP。定义\(f_{i,j,i2,j2}\)表示两个人分别在\((i,j),(i2,j2)\)时获得的最大收益。复杂度\(O(n^4)\),不行。我们换种方法,定义\(f_{st,x,y}\)表示两人同时走了\(st\)步,分别向右走了\(x,y\)步。显然如果向右的步数确定了,向下的也确定了。转移方程如下:\[f_{st,x......
  • 题解 CF1265E
    期望DP。定义\(f_i\)表示第\(i\)个镜子照成功的期望天数,\(p_i\)为第\(i\)天成功的概率,\(q_i\)为第\(i\)天失败的概率。根据题意容易列出方程:\[f_i=(f_{i-1}+1)\cdotp_i+(f_{i-1}+1+f_i)\cdotq_i\]移项得:\[(1-q_i)\cdotf_i=(f_{i-1}+1)\cdot(p_i+q_i)\]同除以......
  • 题解 CF930C
    好题啊好题。定义\(a_i\)为有多少个区间包含\(i\)。拍脑袋一想,当且仅当存在顺序的三个坐标\((i,j,k)\)满足\(a_i>a_j\)且\(a_j<a_l\)时,可以确定没有数被所有区间包含。这个结论很简单,因为如果存在,则\(a\)序列必定为一个“山峰”。而如果出现上面这种情况,说明有“山......
  • 题解 P6772 [NOI2020] 美食家
    观察数据范围,\(T\)很大,\(n\)很小,用矩乘。对于一条边\((u,v,w)\),我们将\(u\)拆成\(w-1\)个点,并连接\((u_0,u_1,0),(u_1,u_2,0)...(u_{w-2},u_{w-1},0)\)和\((u_{w-1},v_0,c_{v})\),总点数\(5n\)。将美食节按时间排序,相邻两个美食节之间用矩阵快速幂转移,然后再加上附加......
  • 题解 CF1202C
    不错的题,需要点思维和码力。容易发现,左右和上下互不影响,可以分开处理,这里以左右举例。定义向左走一格\(-1\),向右走一格\(+1\),求个前缀和找到最大值和最小值,和出现最值的最早时间与最晚时间。定义为\(l,r,l2,r2\)。只有当我们放了一个A或D使得所有最大值\(-1\)且最小值......
  • 题解 P8338 [AHOI2022] 排列
    恶心题。每次操作,相当与把第\(i\)个数置换到\(p_i\),于是可以连边。因为\(i\)和\(p_i\)互不相同,所以对于每一个点,有且仅有一条出边和一条入边,即若干个简单环。那么最少操作\(\operatorname{lcm}(a_1,a_2,a_3...a_{x-2},a_{x-1},a_x)\)次点会都回到原位。其中\(a_i\)......
  • 题解 CF840C On the Bench
    这是一篇简洁易懂的良心题解,提供了多种做法。对于两个数\(x,y\),定义\(x=n^2\cdottx,y=m^2\cdotty\)。如果\(x\cdoty\)为平方数,则说明\(tx=ty\)。所以我们可以将每个数除去其平方因子,比较相邻两数是否相等即可。F1:定义\(f_{i,j,k}\)为插入\(i\)个数、有\(j\)对......
  • 题解 P3803 【模板】多项式乘法(FFT)
    感觉题解区不是写的太高深,就是写的太高深。所以给初中、小学和幼儿园的萌新准备一篇简单易懂的良心题解~前置知识一、多项式的系数表示法和点值表示法。\(A(x)=\sum\limits_{i=0}^{n-1}a_i\cdotx^i\)系数:\((a_0,a_1,a_2...a_{n-2},a_{n-1})\)。点值:\((x_0,y_0),(x_1,y_1)...(......