单点修改树中某个节点,查询子树的性质.DFS序 子树序列一定在父节点的DFS序列之内,所以可以用线段树维护.

 

1:  /*

2:  DFS序 +线段树

3:  */

4:   

5:  #include 
     

6:  #include 
     

7:  #include 
     

8:  #include 
     

9:  #include 
     

10:  #include 
     

11:  using namespace std;

12:   

13:  #define LL(a)   a<<1

14:  #define RR(a)   a<<1|1

15:   

16:  const int MaxL = 200002;

17:   

18:  int pre[MaxL];  // first travel

19:  int nxt[MaxL];  // nxt travel

20:  bool vis[MaxL];

21:  int N;

22:  vector
     
      
        > E(MaxL);
      
     

23:   

24:  struct Seg_tree

25:  {

26:      int left, right;

27:      int sum;

28:  } tt[MaxL<<2];

29:   

30:   

31:  void PushUp(int idx)

32:  {

33:      tt[idx].sum = tt[LL(idx)].sum + tt[RR(idx)].sum;

34:  }

35:   

36:  void build(int l,int r,int idx)

37:  {

38:      tt[idx].left = l, tt[idx].right = r;

39:      tt[idx].sum = r-l+1;

40:      if (l == r) return ;

41:      int m = (l + r) >> 1;

42:      build(l,m, LL(idx));

43:      build(m+1, r, RR(idx));

44:  }

45:   

46:  void update(int p, int idx = 1)

47:  {

48:      if(p == tt[idx].left && p == tt[idx].right)

49:      {

50:          tt[idx].sum ^=1;

51:          return ;

52:      }

53:      int mid = (tt[idx].left + tt[idx].right)>>1;

54:      if(p <= mid) update(p, LL(idx));

55:      else update(p, RR(idx));

56:      PushUp(idx);

57:  }

58:   

59:  int query(int l, int r, int idx = 1)

60:  {

61:      if(l == tt[idx].left && r ==tt[idx].right)

62:          return tt[idx].sum;

63:      int mid = (tt[idx].left + tt[idx].right)>>1;

64:      if(r <= mid) return query(l,r, LL(idx));

65:      else if(l> mid) return query(l,r, RR(idx));

66:      else

67:          return query(l, mid, LL(idx))+ query(mid+1, r, RR(idx));

68:  }

69:   

70:  int mark = 1;

71:  void dfs( int a)

72:  {

73:      vis[a] = 1;

74:      pre[a] = mark++;

75:      for(int i=0; i

76:      {

77:          if(!vis[E[a][i]])

78:              dfs(E[a][i]);

79:      }

80:      nxt[a] = mark++;

81:  }

82:  int main()

83:  {

84:  //    freopen("1.txt","r",stdin);

85:      memset(pre, 0, sizeof(pre));

86:      memset(nxt, 0 ,sizeof(nxt));

87:      memset(vis, 0 ,sizeof(vis));

88:   

89:      scanf("%d", &N);

90:      for(int i=1; i

91:      {

92:          int a,b;

93:          scanf("%d%d", &a,&b);

94:          E[a].push_back(b);

95:          E[b].push_back(a);

96:      }

97:      dfs(1);

98:   

99:      N*=2;

100:      build(1, N, 1);

101:      int M;

102:      scanf("%d", &M);

103:      for(int i=1; i<=M; i++)

104:      {

105:          char c;

106:          int a;

107:          scanf("%s", &c);

108:          scanf("%d",&a);

109:          if(c =='Q')

110:          {

111:              cout<

112:          }

113:          else

114:          {

115:              update(pre[a],1);

116:              update(nxt[a],1);

117:          }

118:      }

119:      return 0;

120:  }