关键是括号序列啊 还有，括号序列上一段代表一棵树，一个点还是代表一个点。 用指针表示图 #include <stdio.h>#include <iostream>#include <queue>#include <algorithm>#include <map>#include <vector>#include <cmath>#include <string.h>usin

题意 给出一个苹果树的一些分叉(x,y)，表示y是x的子节点，给出m次操作，有两种： 1、C x 如果叉x有苹果就摘，没有就长，相当于取反。 2、Q x 查询叉x（包括x）的子节点上一共有多少苹果。 思路 先进行深度优先遍历求出这棵树的先序后序遍历顺序，然后我们进行C操作时就判断然后取反，进行Q操作时就用 f i n d ( e n d [ x ] ) − f i n d ( b e g i

1、http://poj.org/problem?id=3321 2、题目大意： 有一棵树，有n个叉，由n-1条枝条连接，每个叉上最多有一个苹果，假设原来每个叉上都有苹果，现在要对这棵苹果树进行m个操作，其中这m个操作由两种操作组成，C x表示如果x点有苹果就摘掉，没有苹果就长一个，Q x是查询以x结点为根的树有多少个苹果，这道题目看上去好像是普通的树状数组的题目，但是没有顺序，我们需要先按照

题意：一棵苹果树有n个结点，开始时每个结点有一个苹果，这n个结点由m条枝连起来，现执行以下两种操作，C x：如果结点x原来有苹果，则把它摘掉，如果没有，则长出1个苹果。Q x：询问以x为根的树的苹果共几个？ 题目链接：http://poj.org/problem?id=3321 ——>>求一棵子树的和，转化为求一个连续区间的和。用线段树进行维护，时间复杂度为O(max(N, M*log(N))