HDU3887(树dfs序列+树状数组)

Counting Offspring

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2424 Accepted Submission(s): 838

Problem Description
You are given a tree, it’s root is p, and the node is numbered from 1 to n. Now define f(i) as the number of nodes whose number is less than i in all the succeeding nodes of node i. Now we need to calculate f(i) for any possible i.

Input
Multiple cases (no more than 10), for each case:
The first line contains two integers n (0<n<=10^5) and p, representing this tree has n nodes, its root is p.
Following n-1 lines, each line has two integers, representing an edge in this tree.
The input terminates with two zeros.

Output
For each test case, output n integer in one line representing f(1), f(2) … f(n), separated by a space.

Sample Input
15 7
7 10
7 1
7 9
7 3
7 4
10 14
14 2
14 13
9 11
9 6
6 5
6 8
3 15
3 12
0 0

Sample Output
0 0 0 0 0 1 6 0 3 1 0 0 0 2 0

思路： dfs序+树状数组。c++可调整栈的大小.#pragma comment(linker,"/STACK:1024000000,1024000000") 两个1024000000均为字节数。

#pragma comment(linker,"/STACK:1024000000,1024000000")

#include <cstdio>

#include <cstring>

using namespace std;

const int MAXN=;

struct Edge{

    int to,net;

}es[MAXN+MAXN];

int n,root;

int head[MAXN],tot;

int lch[MAXN],rch[MAXN],key;

int bit[MAXN];

int res[MAXN];

void addedge(int u,int v)

{

    es[tot].to=v;

    es[tot].net=head[u];

    head[u]=tot++;

}

void dfs(int u,int fa)

{

    lch[u]=++key;

    for(int i=head[u];i!=-;i=es[i].net)

    {

        int v=es[i].to;

        if(v!=fa)

        {

            dfs(v,u);

        }

    }

    rch[u]=key;

}

void add(int i,int x)

{

    while(i<MAXN)

    {

        bit[i]+=x;

        i+=(i&-i);

    }

}

int sum(int i)

{

    int s=;

    while(i>)

    {

        s+=bit[i];

        i-=(i&-i);

    }

    return s;

}

int main()

{

    while(scanf("%d%d",&n,&root)!=EOF&&(n+root)!=)

    {

        memset(bit,,sizeof(bit));

        memset(head,-,sizeof(head));

        memset(res,,sizeof(res));

        tot=;

        key=;

        for(int i=;i<n-;i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            addedge(u,v);

            addedge(v,u);

        }

        dfs(root,-);

        for(int i=;i<=n;i++)

        {

            res[i]=sum(rch[i])-sum(lch[i]-);

            add(lch[i],);

        }

        for(int i=;i<n;i++)

        {

            printf("%d ",res[i]);

        }

        printf("%d\n",res[n]);

    }

    return ;

}

第二版：

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int MAXN=;

vector<int> arc[MAXN];

int n,root;

int bit[MAXN];

void add(int i,int x)

{

    while(i<MAXN)

    {

        bit[i]+=x;

        i+=(i&(-i));

    }

}

int sum(int i)

{

    int s=;

    while(i>)

    {

        s+=bit[i];

        i-=(i&(-i));

    }

    return s;

}

int res[MAXN],vis[MAXN];

void dfs(int u)

{

    vis[u]=;

    res[u]=sum(u);

    add(u,);

    for(int i=;i<arc[u].size();i++)

    {

        int to=arc[u][i];

        if(!vis[to])

        {

            dfs(to);

        }

    }

    res[u]=sum(u)-res[u]-;

}

int main()

{

    while(scanf("%d%d",&n,&root)!=EOF&&(n||root))

    {

        memset(bit,,sizeof(bit));

        memset(vis,,sizeof(vis));

        for(int i=;i<=n;i++)    arc[i].clear();

        for(int i=;i<n-;i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            arc[u].push_back(v);

            arc[v].push_back(u);

        }

        dfs(root);

        for(int i=;i<n;i++)

        {

            printf("%d ",res[i]);

        }

        printf("%d\n",res[n]);

    }

    return ;

}

巴特西

HDU3887(树dfs序列+树状数组)

最新文章

热门文章