HDU 3887 Counting Offspring

← →

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序+樹狀數組+數組模拟連結清單來存儲樹

# include<stdio.h>
# include<math.h>
# include<string.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")  //防爆棧

struct abc
{
    int next,just;
};
abc f[300000];
int n, e, root;
int frist[100005], c[100005], d[100005];

int add(int x, int y)
{
    f[e].just = y; f[e].next = frist[x]; frist[x] = e++;
    f[e].just = x; f[e].next = frist[y]; frist[y] = e++;
    return 0;
}

int lowb(int t){ return t&(-t); }

int fadd(int x)
{
    while (x <= n) { d[x]++; x += lowb(x); }
    return 0;
}

int sum(int x)
{
    if (x <= 0) return 0;
    return d[x] + sum(x - lowb(x));
}

int ss(int x, int fa)
{
    int a = sum(x);
    int k = frist[x];
    while (k > 0)
    {
        if (f[k].just != fa)
        {
            fadd(f[k].just);
            ss(f[k].just, x);
        }
        k = f[k].next;
    }
    c[x] = sum(x) - a;
    return 0;
}

int main()
{
    while (scanf("%d%d", &n, &root) != EOF&&n+root)
    {
        memset(f,0,sizeof(f));
        memset(frist, 0, sizeof(frist));
        memset(d, 0, sizeof(d));
        e = 1;
        for (int i = 1; i < n; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
        }
        ss(root,root);
        printf("%d", c[1]);
        for (int i =2; i <= n; i++) printf(" %d", c[i]);
        printf("\n");
    }
    return 0;
}      

hdu上這個已經過不了了，隻能手動模拟棧。

# include<stdio.h>
# include<math.h>
# include<string.h> 
# include<stack>
# include<algorithm>
using namespace std;
stack<int> p;

struct wrz
{
  int next, just;
};
wrz f[300000];
int n, e, root;
int frist[100005], c[100005], d[100005], u[100005];

int add(int x, int y)
{
  f[e].just = y; f[e].next = frist[x]; frist[x] = e++;
  f[e].just = x; f[e].next = frist[y]; frist[y] = e++;
  return 0;
}

int lowb(int t){ return t&(-t); }

int fadd(int x)
{
  while (x <= n) { d[x]++; x += lowb(x); }
  return 0;
}

int sum(int x)
{
  if (x <= 0) return 0;
  return d[x] + sum(x - lowb(x));
}

int ss(int x)
{
  p.push(x);  u[x] = 1;
  while (!p.empty())
  {
    begin:int x = p.top();
    if (c[x] == 0) {
      fadd(x);
      c[x] = sum(x);
    }
    int k = frist[p.top()];
    while (k > 0)
    {
      if (u[f[k].just] == 0)
      {
        u[f[k].just] = 1;
        p.push(f[k].just);
        goto begin;
      }
      k = f[k].next;
    }
    c[x] = sum(x) - c[x];
    p.pop();
  }
  return 0;
}

int main()
{
  while (~scanf("%d%d", &n, &root), n + root)
  {
    memset(f, 0, sizeof(f));
    memset(frist, 0, sizeof(frist));
    memset(d, 0, sizeof(d));
    memset(u, 0, sizeof(u));
    memset(c, 0, sizeof(c));
    e = 1;
    for (int i = 1; i < n; i++)
    {
      int a, b;
      scanf("%d%d", &a, &b);
      add(a, b);
    }
    ss(root);
    printf("%d", c[1]);
    for (int i = 2; i <= n; i++) printf(" %d", c[i]);
    printf("\n");
  }
  return 0;
}      

上面這個是用了goto的，下面的是普通的。

# include<stdio.h>
# include<math.h>
# include<string.h> 
# include<stack>
# include<algorithm>
using namespace std;
stack<int> p;

struct wrz
{
  int next, just;
};
wrz f[300000];
int n, e, root;
int frist[100005], c[100005], d[100005], u[100005];

int add(int x, int y)
{
  f[e].just = y; f[e].next = frist[x]; frist[x] = e++;
  f[e].just = x; f[e].next = frist[y]; frist[y] = e++;
  return 0;
}

int lowb(int t){ return t&(-t); }

int fadd(int x)
{
  while (x <= n) { d[x]++; x += lowb(x); }
  return 0;
}

int sum(int x)
{
  if (x <= 0) return 0;
  return d[x] + sum(x - lowb(x));
}

int ss(int x)
{
  p.push(x);  u[x] = 1;
  while (!p.empty())
  {
    int x = p.top();
    if (c[x] == 0) { fadd(x); c[x] = sum(x); }
    for (int k = frist[x]; k; k = f[k].next)
      if (u[f[k].just] == 0)
      {
        u[f[k].just] = 1;
        p.push(f[k].just);
      }
    if (p.top() == x)
    {
      c[x] = sum(x) - c[x];
      p.pop();
    }
  }
  return 0;
}

int main()
{
  while (~scanf("%d%d", &n, &root), n + root)
  {
    memset(f, 0, sizeof(f));
    memset(frist, 0, sizeof(frist));
    memset(d, 0, sizeof(d));
    memset(u, 0, sizeof(u));
    memset(c, 0, sizeof(c));
    e = 1;
    for (int i = 1; i < n; i++)
    {
      int a, b;
      scanf("%d%d", &a, &b);
      add(a, b);
    }
    ss(root);
    printf("%d", c[1]);
    for (int i = 2; i <= n; i++) printf(" %d", c[i]);
    printf("\n");
  }
  return 0;
}