---
tags: DP
title: 樹DP
---

:::info
題目在這裡w
<br>
- [Timus 1018. Binary Apple Tree](https://acm.timus.ru/problem.aspx?space=1&num=1018)
- [CF 178F3](https://codeforces.com/contest/178/problem/F3)
:::

:::success
## 樹DP
- 沒錯，就是在樹上做DP
- [例題](https://acm.timus.ru/problem.aspx?space=1&num=1018)
- $dp[i][j]$ 表示以節點i為根的子樹要保留j條邊的最大蘋果數量
- (全拿左) $$\\dp[i][j] = dp[i.lchild][j-1]+edge[i][i.lchild]$$
- (全拿右) $$\\dp[i][j] = dp[i.rchild][j-1]+edge[i][i.rchild]$$
- (左邊拿k條，右邊拿j-k條)$$dp[i][j] = dp[i.lchild][k-1]+edge[i][i.lchild]\\+ dp[i.rchild][j-k-1]+edge[i][i.rchild]$$ $k \in \{0,1,2,...,j\}$
- 以上三個取最大值
- 時間複雜度（假設最差狀況）：$O(N^3)$（False）
- ~~關於(J, K)如何處理請看此[影片](https://ani.gamer.com.tw/animeVideo.php?sn=22261)
LOVE JK
好想買會員 @peter12345678 養嗎~~
- 其實：
- 第二個維度轉移：
- 如果某個節點只有連出去一條子邊，該轉移為 $O(Q)$
- 最差狀況，完滿二元樹：
- $$ \begin{split} K&=1*\frac{Q}{4}+2*\frac{Q}{16}+4*\frac{Q}{64}+8*\frac{Q}{256} +...\\&=Q(\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\frac{1}{32}+...)\\&=\frac{Q}{2}\end{split} $$
- 時間複雜度（假設最差狀況）：$O(N^2)$（True）
- 另證------數學歸納法：
- 設父節點P的兩個子節點為根的子樹大小為x,y，且複雜度為 $O(x^2), O(y^2)$
- 以P為根的子樹大小為 $p = x+y+1$
- 則以P為根的子樹：
- $x^2（左邊） + y^2（右邊） + xy$（轉移） $\leq x^2+y^2+2xy=(x+y)^2\leq p^2$
- 複雜度為 $O(p^2)$ 得證
:::

# Peter Lee cf rating 4002