E61 树形DP P8744 [蓝桥杯 2021 省 A] 左孩子右兄弟

董晓算法 / 2024-10-07 / 原文

视频链接：E61 树形DP P8744 [蓝桥杯 2021 省 A] 左孩子右兄弟_哔哩哔哩_bilibili

P8744 [蓝桥杯 2021 省 A] 左孩子右兄弟 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 树形DP O(n)
#include <bits/stdc++.h>
using namespace std;

const int N=100005;
int n,f[N],son[N];
int head[N],idx;
struct E{int v,ne;}e[N<<1];
void add(int u,int v){
  e[++idx]={v,head[u]};head[u]=idx;
}

void dfs(int u){
  for(int i=head[u];i;i=e[i].ne){
    int v=e[i].v;
    dfs(v);
    f[u]=max(f[u],f[v]);
  }
  f[u]+=son[u];
}
signed main(){
  cin>>n;
  for(int i=2,u;i<=n;++i)
    cin>>u,add(u,i),++son[u];
  dfs(1);
  cout<<f[1];
}

P8625 [蓝桥杯 2015 省 B] 生命之树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1122 最大子树和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 树形DP O(n)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N=100005;
int n,a[N];
long long f[N];
vector<int> e[N];

void dfs(int u,int fa){
  f[u]=a[u];
  for(int v:e[u]){
    if(v==fa) continue;
    dfs(v,u);
    f[u]+=max(f[v],0ll);
  }
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++)scanf("%d",&a[i]);
  for(int i=1,u,v;i<n;i++){
    scanf("%d%d",&u,&v);
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1,0);
  printf("%lld",max(*max_element(f+1,f+n+1),0ll));
}