daily 2

两道树形dp，说真的最近确实整个身心都放松了，这样下去感觉不太行，啊啊啊啊

CF 219D

我们对应先计算出从1开始需要反转多少条边，然后再从1向下，每次计算以当前点为根需要减去/增加的反转边的条数即可

void solve(){
  int n;
  cin>>n;
  vector<vector<int>>E(n+1),cost(E);
  for(int i=0;i<n-1;++i){
    int u,v;
    cin>>u>>v;
    E[u].push_back(v);
    E[v].push_back(u);
    cost[u].push_back(0);
    cost[v].push_back(1);
  }
  vector<int>dp(n+1);
  function<void(int,int)>dfs1=[&](int x,int f){
    for(int i=0;i<E[x].size();++i){
        int v=E[x][i],c=cost[x][i];
        if(v==f)continue;
        dfs1(v,x);
        dp[x]+=dp[v]+c;
    }
  };
  dfs1(1,0);
  int ans=INT_MAX;
  function<void(int,int)>dfs2=[&](int x,int f){
    for(int i=0;i<E[x].size();++i){
        int v=E[x][i],c=cost[x][i];
        if(v==f)continue;
        dp[v]=dp[x]+(c?-1:1);
        dfs2(v,x);
        ans=min(ans,dp[x]);
        ans=min(ans,dp[v]);//pay attention not to miss calculate it!
    }
  };
  dfs2(1,0);
  cout<<ans<<'\n';
  for(int i=1;i<=n;++i){
    if(dp[i]==ans){
        cout<<i<<' ';
    }
  }
  return;
}

CF 1065F

dp[i]表示从i出发且回到i的最大可访问节点数，ans[i]表示从i出发不需要回到i的最大可访问节点数，转移看代码

void solve(){
  int n,k;
  cin>>n>>k;
  vector<vector<int>>E(n+1);
  for(int i=2;i<=n;++i){
    int p;
    cin>>p;
    E[p].push_back(i);
  }
  vector<int>dp(n+1),dep(n+1),low(n+1),ans(n+1);//dp[i]:the total leaf num it could get if use i to be the root and comes back to i in the end. low[i]:the smallest depth it could get in this senario. ans[i]: the total number could get using i to be the root and did not request to return to the root
  function<void(int,int)>dfs1=[&](int x,int f){
    dep[x]=dep[f]+1;
    if(E[x].size()==0){
        low[x]=dep[x];
        dp[x]=1;
    }else{
        int height=1e9;
        int value=0;
        for(int v:E[x]){
            if(v==f)continue;
            dfs1(v,x);
            if(low[v]-dep[x]<=k){
                value+=dp[v];
                height=min(height,low[v]);
            }
        }
        dp[x]=value;
        low[x]=height;
    }
  };
  dfs1(1,0);
  function<void(int,int)>dfs2=[&](int x,int f){
    ans[x]=dp[x];
    for(int v:E[x]){
        if(v==f)continue;
        dfs2(v,x);
        int tmp=dp[x];
        if(low[v]-dep[x]<=k)tmp-=dp[v];
        ans[x]=max(ans[x],tmp+ans[v]);
    }
  };
  dfs2(1,0);
  cout<<ans[1]<<'\n';
  return;
}