poj 3321 Apple Tree (Binary Index Tree)

　　做回之前个人赛超时到比赛结束的题。

　　这题就是一个简单的树形结构转化为线性结构，然后套用树状数组求区间和。不过不知道什么原因，用vector构建邻接表在dfs的时候超时了，转成链表就360ms过了。对于才1e5条边这么小的规模，我还是第一次遇见STL会超时的。

代码如下：

View Code

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <cstring>
  6 
  7 using namespace std;
  8 
  9 #define REP(i, n) for (int i = 0; i < (n); i++)
 10 #define REP_1(i, n) for (int i = 1; i <= (n); i++)
 11 #define PB push_back
 12 #define _clr(x) memset(x, 0, sizeof(x))
 13 #define SZ(x) ((int) (x).size())
 14 typedef vector<int> VI;
 15 
 16 const int N = 1e5 + 100;
 17 //VI rel[N];
 18 int bg[N], ed[N];
 19 bool vis[N];
 20 int ebg[N], enxt[N << 1], eadj[N << 1], edgeCnt;
 21 int bit[N], bitSZ;
 22 
 23 void init(int n) {
 24     _clr(bit);
 25     edgeCnt = 0;
 26     REP_1(i, n) {
 27         ebg[i] = enxt[i] = -1;
 28     }
 29 }
 30 
 31 void addedge(int u, int v) {
 32     eadj[edgeCnt] = v;
 33     enxt[edgeCnt] = ebg[u];
 34     ebg[u] = edgeCnt++;
 35 }
 36 
 37 void add2edge(int u, int v) {
 38     addedge(u, v);
 39     addedge(v, u);
 40 }
 41 
 42 void input(int n) {
 43     REP_1(i, n)
 44 //        rel[i].clear(),
 45         vis[i] = false;
 46     n--;
 47     int x, y;
 48     REP(i, n) {
 49         scanf("%d%d", &x, &y);
 50 //        rel[x].PB(y);
 51 //        rel[y].PB(x);
 52         add2edge(x, y);
 53     }
 54 }
 55 
 56 void add(int x, int d) {
 57     for (; x <= bitSZ; x += (-x) & (x)) {
 58         bit[x] += d;
 59     }
 60 }
 61 
 62 int sum(int x) {
 63     int ret = 0;
 64     for (; x > 0; x -= (-x) & x) {
 65         ret += bit[x];
 66     }
 67     return ret;
 68 }
 69 
 70 int curID;
 71 
 72 void dfs(int x) {
 73     add(curID, 1);
 74     vis[x] = true;
 75 //    int sz = SZ(rel[x]);
 76     int t;
 77     bg[x] = curID++;
 78 //    REP(i, sz) {
 79     for (int eid = ebg[x]; ~eid; eid = enxt[eid]) {
 80 //        t = rel[x][i];
 81         t = eadj[eid];
 82         if (vis[t]) continue;
 83         dfs(t);
 84     }
 85     ed[x] = curID;
 86 }
 87 
 88 void makeList(int n) {
 89     curID = 1;
 90     dfs(1);
 91 //    REP_1(i, n) {
 92 //        cout << i << ": " << bg[i] << ' ' << ed[i] << endl;
 93 //    }
 94 }
 95 
 96 int sum(int l, int r) {
 97     return sum(r) - sum(l);
 98 }
 99 
100 int main() {
101 //    freopen("in", "r", stdin);
102     int n, x;
103     char buf[3];
104     while (~scanf("%d", &n)) {
105         bitSZ = n;
106         init(n);
107         input(n);
108         makeList(n);
109         scanf("%d", &n);
110         REP(i, n) {
111             scanf("%s%d", buf, &x);
112             if (buf[0] == 'Q') {
113 //                cout << bg[x] - 1 << ' ' << ed[x] - 1 << endl;
114                 printf("%d\n", sum(bg[x] - 1, ed[x] - 1));
115             } else {
116 //                cout << "~~ " << bg[x] << endl;
117                 if (vis[x]) {
118                     add(bg[x], -1);
119                     vis[x] = false;
120                 } else {
121                     add(bg[x], 1);
122                     vis[x] = true;
123                 }
124             }
125         }
126     }
127     return 0;
128 }

——written by Lyon