描述

一棵樹上有n個節點，編號分別為1到n，每個節點都有一個權值w。我們將以下面的形式來要求你對這棵樹完成一些操作： I. CHANGE u t : 把結點u的權值改為t II. QMAX u v: 詢問從點u到點v的路徑上的節點的最大權值 III. QSUM u v: 詢問從點u到點v的路徑上的節點的權值和. 注意：從點u到點v的路徑上的節點包括u和v本身.

---

分析

學了樹鏈剖分就能做的題目.

---

• 一個查詢和操作和一個查詢最大值操作, 中間的步驟不一樣. 可以寫兩個函數, 返回值初始化的時候不一樣, QSUM的時候初始化為0, QMAX的時候初始化的時候初始化為 -INF.

---

• 想不通過樹鏈剖分直接調用線段樹 (比如本題的修改操作, 因為是單點修改), 修改的不是x而是tid[x]也就是x的新編號. 因為線段樹里的編號是重新編的.

---

代碼

https://code.csdn.net/snippets/607983

INF 可以設為 0x3f3f3f3f, 這樣 memset(0x3f) 后數組初始值都等于 0x3f3f3f3f. 比較好的性質. ——Archon

一堆宏, 寫熟了很好用. ——Archon

總結

以上是生活随笔為你收集整理的BZOJ-1036-树的统计Count的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。