[TIOJ] 1711. Apple Tree
題目連結: http://tioj.infor.org/problems/1711 說個笑話，oToToT會寫程式。 搞了好久都不會做，然後一直假解QAQ 去網路上查到momo學長的解居然也是錯的（詳見底下測資） 10 6 522 288 963 788 756 856 18 412 378 789 2 1 3 2 4 2 5 2 6 5 7 6 8 4 9 1 10 4 最後是去問了minson才知道一個怪怪的解QQ，我到現在還是不知道這為何是好的(他說複雜度是$O(N^2)$)，可能跟CF 729F有類的概念吧。 註(2019/04/24):似乎是因為某種兩個東西只會在他們的LCA被合起來 總之就是用一個顯然的事實就是我們一個(子)樹最多只能走他底下size步，所以我們就只要維護size，並且每次上界都用當前大小做dp即可。 dp狀態也很簡單 $ dp[i][j][0] := \text{第i個節點走j步後且要走回來的最大值}, dp[i][j][1] := \text{第i個節點走j步後，停在他底下某個人的最大值} $轉移就直接暴力混和背包即可。 #include <cstdio> #include <cstring> #include <vector> #include <algorithm> const int N = 1000 + 5; int w[N], dp[N][N<<1][2]; int tmp[N<<1][2], sz[N]; std::vector<int> G[N]; void dfs(int,int,int); int main(){ int n, k; scanf("%d%d", &n, &k); k = std::min(k, n+n); for(int i=1;i<=n;i++) scanf("%d", w+i); for(int i=1;i<n;i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u);