Loading... [链接标题](https://www.luogu.org/problemnew/show/P1122 "链接标题") <!--more--> * * * * 树形dp * 统计出每个子树的大小，求max \- 回溯时$f\[x\]=max(0,f\[x_{son}\])$ ---------------------------------- #### 代码如下 ```cpp #include<bits/stdc++.h> using namespace std; const int N=16009; vector<int> son[N]; int v[N],n,maxn=-0x3f3f3f3f,f[N]; void dp(int x,int fa){ f[x]=v[x]; for(int i=0;i<son[x].size();i++){ int y=son[x][i]; if(y==fa) continue; dp(y,x); f[x]+=max(0,f[y]); } maxn=max(maxn,f[x]); } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>v[i]; } for(int i=1;i<n;i++){ int a,b; cin>>a>>b; son[a].push_back(b); son[b].push_back(a); } dp(1,0); cout<<maxn; return 0; } ``` Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏