Counting Offspring

 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 #include <cmath>10 #include <string>11 #include <cstdio>12 #include <vector>13 #include <fstream>14 #include <cstring>15 #include <iostream>16 #include <algorithm>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<int> 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 }

 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 #include <stack> 9 #include <cmath>10 #include <string>11 #include <cstdio>12 #include <vector>13 #include <fstream>14 #include <cstring>15 #include <iostream>16 #include <algorithm>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<int> g[maxn];24 stack<int> 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 }