daily 2

两道树形dp水题

CF 161D

dp[x][i]表示和当前点x距离为i，且在x的子树中的节点数量
我们通过乘法原理可以直接求出，但是注意不要重复计算，所以当我们把前一颗子树的值计算完成后再计算当前的值

void solve(){
  int n,k;
  cin>>n>>k;
  vector<vector<int>>E(n+1);
  for(int i=0;i<n-1;++i){
    int u,v;
    cin>>u>>v;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  vector dp(n+1,vector<int>(k+1));
  int ans=0;
  function<void(int,int)>dfs=[&](int x,int f){
    dp[x][0]=1;
    for(int v:E[x]){
        if(v==f)continue;
        dfs(v,x);
        for(int i=0;i<k;++i){
            ans+=dp[x][i]*dp[v][k-i-1];
        }
        for(int i=1;i<=k;++i){
            dp[x][i]+=dp[v][i-1];
        }
    }
  };
  dfs(1,-1);
  cout<<ans<<'\n';
  return;
}

CF 1083A
dp[x]表示从当前的点x出发，可以获得的最大汽油是多少，那么转移就是
${dp[x]=max(dp[x],dp[v]+W[x]-c)}$

#define int ll
void solve(){
  int n;
  cin>>n;
  vector<int>W(n+1);
  for(int i=1;i<=n;++i)cin>>W[i];
  vector<vector<int>>E(n+1),cost(E);
  for(int i=0;i<n-1;++i){
    int u,v,c;
    cin>>u>>v>>c;
    E[u].push_back(v);
    E[v].push_back(u);
    cost[u].push_back(c);
    cost[v].push_back(c);
  }
  vector<int>dp(n+1);
  int ans=0;
  function<void(int,int)>dfs=[&](int x,int f){
    dp[x]=W[x];
    ans=max(ans,dp[x]);
    for(int i=0;i<E[x].size();++i){
        int c=cost[x][i];
        int v=E[x][i];
        if(v==f)continue;
        dfs(v,x);
        ans=max(ans,dp[v]+dp[x]-c);
        dp[x]=max(dp[x],dp[v]+W[x]-c);
    }
  }; 
  dfs(1,0);
  cout<<ans<<'\n';   
  return;
}