A simple Blog for wyx I've been down the bottle hoping.
JLOI2014 树 队列和栈
发表于: | 分类: Oi | 评论:0 | 阅读:38

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

我们可以维护这样一个数据结构,他的前半部分是一个保留原来信息的队列
后半部分是一个栈
DFS一遍,当深搜到一个点时将这个点加入队列,同时队头向后调整,使队列中元素之和 $<=s$ ,等于 $s$ 记录 $ans$ 。
当一个点出栈时将队尾删除,同时队头向前调整,使队列中元素之和刚好 $<=s$

这算是栈和队列的结合使用了……

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 100000+5
#define M 200000+5
using namespace std;


int n,r,h,s;
int a[N],q[N],fa[N];
int head[N];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x);
    head[y] = cnt;
}

int sum;
int ans ;

void DFS(int x)
{
    q[++r] = a[x];
    sum += a[x];
    while(sum>s)
        sum-=q[++h];
    if(sum==s)++ans;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa[x])
        {
            fa[edge[i].to] = x;
            DFS(edge[i].to);
        }
    sum-=q[r--];
    while(h && sum + q[h]<=s)
        sum += q[h--];
}

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<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    cin >> n >> s;
    for(int i=1;i<=n;++i)
        a[i] = read();
    for(int i=1;i<n;++i)
    {
        int x = read() , y = read();
        add(x,y);
    }
    DFS(1);
    cout<<ans<<endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP