【NOIP无压力模拟赛2】苹果树
Description
xth种了一棵苹果树，这棵树由n个节点构成，中间有树枝连接，苹果都会长在节点上，并且不会有两个苹果长在同一个节点上。Xth想知道某个子树上有多少个苹果，你能帮帮他吗？（1号节点为跟）
Input
第一行：一个整数n，表示苹果树有n个节点。
以下n-1行：每行两个整数u、v，表示u、v两节点间有树枝相连。
第n+1行：一个整数m，表示有m个询问或操作。
以下m行：一个字符（’C’或’Q’）和一个整数x。‘C’表示将x节点处的苹果有无情况取反。‘Q’表示询问以x为根的子树中苹果的个数。
注：苹果树开始时是长满苹果的。
Output
对于每一个询问输出一行，一个整数，表示苹果数。
Sample Input
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
143 1 2 1 3 3 Q 1 C 2 Q 1
Sample Output
复制代码
1
2
3
43 2
Hint
N<=100000,M<=100000
分析：
题目给出的是一棵树，要求的是一颗子树（可视为区间）的和，还要求动态修改，这在树上不好实现。
一般多叉树有那些处理方法？①拓扑排序②深搜。拓扑排序在这里肯定是行不通。
复制代码
1题目中原来的编号顺序没有什么卵用，不妨从根开始深搜，按照探访的顺序编号，一颗子树必定对应着一段连续的区间
复制代码
1[L,R]，L就是根节点。
复制代码
1现在要做的就是修改+查询区间和，当然用树状数组实现。
复制代码
1代码如下：
复制代码
。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159复制代码#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<cstring> #include<queue> #include<vector> #include<algorithm> #define LL long long #define CLEAR(xxx) memset(xxx,0,sizeof(xxx)) using namespace std; const int maxn=100000+5,inf=1e9; int n,m,e,tot,L[maxn],R[maxn],s[maxn],c[maxn]; int to[maxn<<2],Next[maxn<<2],last[maxn]; inline int lowbit(int x) {return x&-x;} inline void _read(int &x){ char ch=getchar(); bool mark=false; for(;!isdigit(ch);ch=getchar())if(ch=='-')mark=true; for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0'; if(mark)x=-x; } void Add(int x,int d){ for(;x<=n;x+=lowbit(x)) c[x]+=d; } int Sum(int x){ int ans; for(ans=0;x>0;x-=lowbit(x)) ans+=c[x]; return ans; } void add_edge(int From,int To){ Next[++e]=last[From]; last[From]=e; to[e]=To; } void DFS(int v,int fa){ L[v]=++tot; //开始探访v为根的子树 for(int i=last[v];i;i=Next[i]){ if(to[i]==fa) continue; DFS(to[i],v); } R[v]=tot; //v为根的子树探访完毕，记下结尾编号 } int main(){ int i,x,y,p; _read(n); for(i=1;i<n;i++){ _read(x); _read(y); add_edge(x,y); add_edge(y,x); } DFS(1,0); for(i=1;i<=n;i++){ //开始挂满了苹果 s[i]=1; Add(i,1); } _read(m); while(m--){ char ch; cin>>ch; _read(p); if(ch=='C'){ p=L[p]; if(s[p]==1)Add(p,-1); else Add(p,1); s[p]=1-s[p]; } else { printf("%dn",Sum(R[p])-Sum(L[p]-1)); } } return 0; } /* */
最后
以上就是调皮牛排最近收集整理的关于苹果树 nkoj 2358/ poj 3321的全部内容，更多相关苹果树内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复