Counting Offspring
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1757 Accepted Submission(s): 582
Problem DescriptionYou 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.
InputMultiple 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.
OutputFor each test case, output n integer in one line representing f(1), f(2) … f(n), separated by a space.
Sample Input15 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 Output0 0 0 0 0 1 6 0 3 1 0 0 0 2 0
可以直接dfs（需要手工加栈）
Accepted Code:
1 /************************************************************************* 2 > File Name: 3887.cpp 3 > Author: Stomach_ache 4 > Mail: sudaweitong@gmail.com 5 > Created Time: 2014年08月09日 星期六 14时11分33秒 6 > Propose: 7 ************************************************************************/ 8 #pragma comment(linker, "/STACK:1024000000,1024000000") 9 #include10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 using namespace std;18 const int maxn = 100002;19 int n, p;20 int ans[maxn], c[maxn], tmp[maxn];21 bool vis[maxn];22 vector g[maxn];23 24 int lowbit(int x) {25 return x & -x;26 }27 28 int sum(int x) {29 int res = 0;30 while (x > 0) {31 res += c[x];32 x -= lowbit(x);33 }34 return res;35 }36 37 void add(int x, int v) {38 while (x <= n) {39 c[x] += v;40 x += lowbit(x);41 }42 }43 44 void dfs(int u, int fa) {45 tmp[u] = sum(u-1);46 for (int i = 0; i < (int)g[u].size(); i++) {47 int v = g[u][i];48 if (v == fa) continue;49 add(v, 1);50 dfs(v, u);51 } 52 ans[u] = sum(u-1) - tmp[u];53 }54 55 int main(void) {56 while (~scanf("%d %d", &n, &p)) {57 if (n == 0 && p == 0) return 0;58 for (int i = 1; i <= n; i++) g[i].clear();59 int x, y;60 for (int i = 1; i < n; i++) {61 scanf("%d %d", &x, &y);62 g[x].push_back(y);63 g[y].push_back(x);64 }65 memset(c, 0, sizeof(c));66 dfs(p, -1);67 for (int i = 1; i <= n; i++) 68 printf("%d%c", ans[i], i == n ? '\n' : ' ');69 }70 return 0;71 }
附上模拟栈的AC代码：
1 /************************************************************************* 2 > File Name: 3887.cpp 3 > Author: Stomach_ache 4 > Mail: sudaweitong@gmail.com 5 > Created Time: 2014年08月09日 星期六 14时11分33秒 6 > Propose: 7 ************************************************************************/ 8 #include9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 using namespace std;18 const int maxn = 100002;19 int n, p;20 int ans[maxn], c[maxn*2], l[maxn], r[maxn], cur[maxn];21 int len;22 bool vis[maxn];23 vector g[maxn];24 stack S;25 26 int lowbit(int x) {27 return x & -x;28 }29 30 int sum(int x) {31 int res = 0;32 while (x > 0) {33 res += c[x];34 x -= lowbit(x);35 }36 return res;37 }38 39 void add(int x, int v) {40 while (x <= len) {41 c[x] += v;42 x += lowbit(x);43 }44 }45 46 void dfs(int u) {47 memset(vis, false, sizeof(vis));48 memset(cur, 0, sizeof(cur));49 while (!S.empty()) S.pop();50 S.push(u);51 len = 0;52 while (!S.empty()) {53 int now = S.top();54 if (!vis[now]) {55 vis[now] = true;56 l[now] = ++len;57 }58 bool flag = false;59 for (int& i = cur[now]; i < (int)g[now].size(); i++) {60 int v = g[now][i];61 if (!vis[v]) {62 S.push(v);63 flag = true;64 break;65 }66 }67 if (flag) continue;68 if (vis[now]) {69 r[now] = ++len;70 S.pop();71 }72 }73 }74 75 int main(void) {76 while (~scanf("%d %d", &n, &p)) {77 if (n == 0 && p == 0) return 0;78 for (int i = 1; i <= n; i++) g[i].clear();79 int x, y;80 for (int i = 1; i < n; i++) {81 scanf("%d %d", &x, &y);82 g[x].push_back(y);83 g[y].push_back(x);84 }85 memset(c, 0, sizeof(c));86 dfs(p);87 for (int i = 1; i <= n; i++) {88 ans[i] = sum(r[i]-1) - sum(l[i]);89 add(l[i], 1);90 }91 for (int i = 1; i <= n; i++) 92 printf("%d%c", ans[i], i == n ? '\n' : ' ');93 }94 return 0;95 }