ZOJ3686 A Simple Tree Problem

　　原题链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4969

　　这题请教了牛B的安神才会了。

　　这道题是线段树的题目，解题思路是把一颗树及其子树用线段（区间）来表示，然后对区间进行修改查询操作。我的具体做法是这样的：对整棵树进行先序遍历，也就是一趟dfs，遍历过程中记录下访问节点的时间戳，那么dfs访问前和递归回来的往返过程得到两个时间点（id[i].l, id[i].r），也就是我们所转换成的区间的端点，由于是先序遍历，那么一棵子树内所有节点是连续的，则最后根节点的区间必定包含其子树节点的区间，这样就构成了线段树，然后对区间进行修改和查询这两项基本操作。

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #include <vector>
  5 #include <iostream>
  6 #define lson (cur << 1)
  7 #define rson (cur << 1 | 1)
  8 using namespace std;
  9 
 10 const int maxn = 100000 + 5;
 11 vector<int> vt[maxn];
 12 int n, m;
 13 int t; // 时间戳
 14 int lazy[maxn << 3];
 15 
 16 struct node
 17 {
 18     int l, r;   // 区间左右端点
 19     int sum;    // 子树1的个数
 20 }tree[maxn << 3], id[maxn];
 21 
 22 void init()
 23 {
 24     t = 1;
 25     for(int i = 1; i <= n; i++)
 26         vt[i].clear();
 27 }
 28 
 29 void dfs(int cur)
 30 {
 31     int size = vt[cur].size();
 32     id[cur].l = t++;
 33     for(int i = 0; i < size; i++)
 34     {
 35         dfs(vt[cur][i]);
 36     }
 37     id[cur].r = t++;
 38 }
 39 
 40 void pushdown(int cur)
 41 {
 42     if(lazy[cur])
 43     {
 44         lazy[lson] ^= 1;
 45         lazy[rson] ^= 1;
 46         tree[lson].sum = tree[lson].r + 1 - tree[lson].l - tree[lson].sum;
 47         tree[rson].sum = tree[rson].r + 1 - tree[rson].l - tree[rson].sum;
 48         lazy[cur] = 0;
 49     }
 50 }
 51 
 52 void pushup(int cur)
 53 {
 54     tree[cur].sum = tree[lson].sum + tree[rson].sum;
 55 }
 56 
 57 void query(int cur, int s, int t, int &ans)
 58 {
 59     int l = tree[cur].l, r = tree[cur].r;
 60     if(l >= s && r <= t)
 61     {
 62         ans += tree[cur].sum;
 63         return ;
 64     }
 65     pushdown(cur);
 66     int mid = (l + r) >> 1;
 67     if(mid >= s)
 68         query(lson, s, t, ans);
 69     if(mid + 1 <= t)
 70         query(rson, s, t, ans);
 71     pushup(cur);
 72 }
 73 void operate(int cur, int s, int t)
 74 {
 75     int l = tree[cur].l, r = tree[cur].r;
 76     if(l >= s && r <= t)
 77     {
 78         lazy[cur] ^= 1;
 79         tree[cur].sum = tree[cur].r + 1 - tree[cur].l - tree[cur].sum;
 80         return ;
 81     }
 82     pushdown(cur);
 83     int mid = (l + r) >> 1;
 84     if(mid >= s)
 85         operate(lson, s, t);
 86     if(mid + 1 <= t)
 87         operate(rson, s, t);
 88     pushup(cur);
 89 }
 90 
 91 void buildTree(int cur, int l, int r)
 92 {
 93     tree[cur].l = l, tree[cur].r = r;
 94     tree[cur].sum = 0;
 95     lazy[cur] = 0;
 96     if(l == r)
 97         return ;
 98     int mid = (l + r) >> 1;
 99     buildTree(lson, l, mid);
100     buildTree(rson, mid+1, r);
101 }
102 
103 int main()
104 {
105     int fa;
106     while(scanf("%d%d", &n, &m) == 2)
107     {
108         init();
109         buildTree(1, 1, n << 1);
110         for(int i = 2; i <= n; i ++)
111         {
112             scanf("%d", &fa);
113             vt[fa].push_back(i);
114         }
115         dfs(1);
116         char ord[5];
117         int p, ans;
118         while(m--)
119         {
120             scanf("%s%d", ord, &p);
121             if(ord[0] == 'o')
122                 operate(1, id[p].l, id[p].r);
123             else
124             {
125                 ans = 0;
126                 query(1, id[p].l, id[p].r, ans);
127                 printf("%d\n", ans >> 1);
128             }
129         }
130         putchar('\n');
131     }
132     return 0;
133 }