poj 3321 Apple Tree

<a target="_blank" href="http://poj.org/problem?id=3321">點選打開poj 3321</a>

思路: 樹狀數組

分析:

1 題目給定一棵樹，然後有n個樹枝，每個樹枝上面初始化有1個蘋果，現在有m個操作

2 題目給定的是一棵樹，我們應該考慮怎麼把這棵樹映射成一個數組，并且跟節點和兒子節點的編号是連續的。這一步我們可以利用dfs來做，利用時間撮的概念，第一次到達的時間作為起始的時間，第二次到達的時間為終點的時間，下圖就是一個例子

、

3 這一題的時間卡vector卡的緊，是以我們應該利用鄰接表來存儲圖

4 當我們求出了每一個節點的時間戳之後，那麼我們就可以利用樹狀數組來求，每一個點的時間戳區間就是這個節點的所有子樹包括本身的和，那麼這個和可以利用樹狀數組進行求解，更新的時候由于我們隻要更新起始位置即可，這樣能夠保證是對的

代碼: