首页 > 代码库 > 【BZOJ2783】[JLOI2012]树 DFS+栈+队列

【BZOJ2783】[JLOI2012]树 DFS+栈+队列

2024-09-11 23:42:26   215人阅读

【BZOJ2783】[JLOI2012]树

Description

       在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的儿子节点的深度为1。路径不必一定从根节点开始。

Input

       第一行是两个整数N和S，其中N是树的节点数。

       第二行是N个正整数，第i个整数表示节点i的正整数。

       接下来的N-1行每行是2个整数x和y，表示y是x的儿子。

Output

       输出路径节点总和为S的路径数量。

Sample Input

3 3
1 2 3
1 2
1 3

Sample Output

2

HINT

对于100%数据，N≤100000，所有权值以及S都不超过1000。

题解：本题可以用各种O(nlogn)的算法水过，但是O(n)当然也可以搞~

用我们在DFS的时候，始终维护这样一个队列，使它是一条连续的链，且队列中点的权值和不超过S，具体做法如下

在DFS进栈的时候，我们将这个点压入队尾，并不断弹出队首直到队列的权值和≤S，并更新答案

在DFS弹栈的时候，我们将这个点从队尾弹出，并将队列恢复成这个点进栈之前的样子（由于后进来的元素都在这个点之后，所以不会修改队列中这个点前面的点，所以只需要记录一下当时的队首位置就行了）

#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int maxn=100010;int n,m,cnt,h,t,top,ans;int fa[maxn],to[maxn],next[maxn],v[maxn],head[maxn],q[maxn],dep[maxn];void add(int a,int b){	to[cnt]=b;	next[cnt]=head[a];	head[a]=cnt++;}void dfs(int x){	int temp=h,i;	q[++t]=x;	while(dep[x]-dep[q[h]]>m)	h++;	if(dep[x]-dep[q[h]]==m)	ans++;	for(i=head[x];i!=-1;i=next[i])	{		dep[to[i]]=dep[x]+v[to[i]];		dfs(to[i]);	}	h=temp,t--;}int main(){	scanf("%d%d",&n,&m);	int i,a,b,c;	for(i=1;i<=n;i++)	scanf("%d",&v[i]);	memset(head,-1,sizeof(head));	for(i=1;i<n;i++)	{		scanf("%d%d",&a,&b);		add(a,b);	}	dep[1]=v[1],h=0,t=0,dfs(1);	printf("%d",ans);	return 0;}

【BZOJ2783】[JLOI2012]树 DFS+栈+队列


联系
我们