suoi14 子树查找 (dfs)
2024-10-19 03:35:44
把询问记下来,然后开个桶差分
#include<bits/stdc++.h>
#define pa pair<int,int>
#define lowb(x) ((x)&(-(x)))
#define REP(i,n0,n) for(i=n0;i<=n;i++)
#define PER(i,n0,n) for(i=n;i>=n0;i--)
#define MAX(a,b) ((a>b)?a:b)
#define MIN(a,b) ((a<b)?a:b)
#define CLR(a,x) memset(a,x,sizeof(a))
#define rei register int
using namespace std;
typedef long long ll;
const int maxn=1e6+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,v[maxn],q[maxn];
int ch[maxn],hd[maxn];
int cnt[maxn],ans[maxn]; void dfs(int x,int f){
int cc=cnt[q[x]];cnt[v[x]]++;
for(int i=hd[x];i;i=ch[i]){
if(i==f) continue;
dfs(i,x);
}ans[x]=cnt[q[x]]-cc;
} int main(){
//freopen(".in","r",stdin);
rei i,j,k;
N=rd();
for(i=;i<=N;i++) v[i]=rd(),q[i]=rd();
for(i=;i<=N;i++){
int a=rd();
ch[i]=hd[a];hd[a]=i;
}
dfs(,);
for(i=;i<=N;i++) printf("%d\n",ans[i]);
return ;
}
最新文章
- Python学习笔记(3)
- window跳转页面
- Bootstrap结合BootstrapTable的使用,分为两种模试显示列表。 自适应表格
- php处理数组函数大全
- Nunit 使用介绍
- 引擎设计跟踪(九.14.2g) 将GNUMake集成到Visual Studio
- Splay Tree的删除操作
- C# dataGridView不显示默认行的解决办法
- 北京西服定做_衬衫定制_关于我们_Dimoon TLR.
- AleNet模型笔记
- Spring Security OAuth2 Demo -- good
- git如何设置ssh密钥
- flask flash消息
- USART of STM32
- mybatis进阶--mapper输入映射和输出映射
- boost::unique_lock和boost::lock_guard的区别
- Linux文本处理工具——Sed
- bzoj千题计划284:bzoj2882: 工艺
- 理解js事件循环(event loop)
- SpringBoot整合定时任务task