Hdu 3887树状数组+模拟栈

题目链接

可以直接dfs（需要手工加栈）

Accepted Code:

 /*************************************************************************

     > File Name: 3887.cpp

     > Author: Stomach_ache

     > Mail: [email protected]

     > Created Time: 2014年08月09日 星期六 14时11分33秒

     > Propose:

  ************************************************************************/

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

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <vector>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 int n, p;

 int ans[maxn], c[maxn], tmp[maxn];

 bool vis[maxn];

 vector<int> g[maxn];

 int lowbit(int x) {

       return x & -x;

 }

 int sum(int x) {

       int res = ;

     while (x > ) {

           res += c[x];

         x -= lowbit(x);

     }

     return res;

 }

 void add(int x, int v) {

       while (x <= n) {

           c[x] += v;

         x += lowbit(x);

     }

 }

 void dfs(int u, int fa) {

       tmp[u] = sum(u-);

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

           int v = g[u][i];

           if (v == fa) continue;

           add(v, );

           dfs(v, u);

     }

     ans[u] = sum(u-) - tmp[u];

 }

 int main(void) {

       while (~scanf("%d %d", &n, &p)) {

           if (n ==  && p == ) return ;

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

         int x, y;

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

             scanf("%d %d", &x, &y);

             g[x].push_back(y);

             g[y].push_back(x);

         }

         memset(c, , sizeof(c));

         dfs(p, -);

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

               printf("%d%c", ans[i], i == n ? '\n' : ' ');

     }

     return ;

 }

附上模拟栈的AC代码：

 /*************************************************************************

     > File Name: 3887.cpp

     > Author: Stomach_ache

     > Mail: [email protected]

     > Created Time: 2014年08月09日 星期六 14时11分33秒

     > Propose:

  ************************************************************************/

 #include <stack>

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <vector>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 int n, p;

 int ans[maxn], c[maxn*], l[maxn], r[maxn], cur[maxn];

 int len;

 bool vis[maxn];

 vector<int> g[maxn];

 stack<int> S;

 int lowbit(int x) {

       return x & -x;

 }

 int sum(int x) {

     int res = ;

     while (x > ) {

         res += c[x];

         x -= lowbit(x);

     }

     return res;

 }

 void add(int x, int v) {

     while (x <= len) {

         c[x] += v;

         x += lowbit(x);

     }

 }

 void dfs(int u) {

     memset(vis, false, sizeof(vis));

     memset(cur, , sizeof(cur));

     while (!S.empty()) S.pop();

     S.push(u);

     len = ;

     while (!S.empty()) {

         int now = S.top();

         if (!vis[now]) {

             vis[now] = true;

             l[now] = ++len;

         }

         bool flag = false;

         for (int& i = cur[now]; i < (int)g[now].size(); i++) {

               int v = g[now][i];

               if (!vis[v]) {

                 S.push(v);

                 flag = true;

                 break;

             }

         }

         if (flag) continue;

         if (vis[now]) {

             r[now] = ++len;

             S.pop();

         }

     }

 }

 int main(void) {

       while (~scanf("%d %d", &n, &p)) {

         if (n ==  && p == ) return ;

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

         int x, y;

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

             scanf("%d %d", &x, &y);

             g[x].push_back(y);

             g[y].push_back(x);

         }

         memset(c, , sizeof(c));

         dfs(p);

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

             ans[i] = sum(r[i]-) - sum(l[i]);

             add(l[i], );

         }

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

             printf("%d%c", ans[i], i == n ? '\n' : ' ');

     }

     return ;

 }