首页 > 其他分享 >树形DP做题回顾(上)

树形DP做题回顾(上)

时间：2024-09-10 22:22:22浏览次数：9  
标签：idx int siz ne fa 树形 做题 include DP

题目一 

​​​​Problem - 2196

大致意思就是求每个点为根的最大深度；

对于这个问题，很快速的我们可以想到跑两次dfs，第一次预处理出以u为根的子树的第一，二深的深度，第二次dfs进行树形dp，从u->v时推出v的最大深度，用up[v]来存储；

代码如下：注意分走到第一大和第二大的路径上的决策，以及up[v]最大值可能出现在d1[v];

#include<iostream>
#include<cstring>
using namespace std;

const int N=1e4+10,M=N*2;
int d1[N],d2[N];

int h[N],e[M],w[M],ne[M],idx;
int vis[N];
int up[N];
void add(int a, int b, int c){
    e[++idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx;
}

void dfs1(int u, int fa){
    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        int dis=w[i];
        if(v==fa)continue;
        dfs1(v,u);
        if(d1[u]<d1[v]+dis){
            d2[u]=d1[u];
            d1[u]=d1[v]+dis;
            vis[u]=v;
        }else if(d2[u]<=d1[v]+dis)d2[u]=d1[v]+dis;
    }
}


void dfs2(int u, int fa){
    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        int dis=w[i];
        if(v==fa)continue;
        if(v==vis[u]){
            up[v]=max(up[u],d2[u])+dis;
        }else{
            up[v]=max(up[u],d1[u])+dis;
        }
        dfs2(v,u);
    }
    up[u]=max(up[u],d1[u]);
    h[u]=0;
}
int main(){
  
    int n;
    while(cin>>n){
        idx=0;
        for(int i=2; i<=n; i++){
            int a,b;
            cin>>a>>b;
            add(a,i,b);
            add(i,a,b);
        }
        int root=1;
        dfs1(root,0);
        dfs2(root,0);
        for(int i=1; i<=n; i++){
            cout<<up[i]<<endl;
            d1[i]=d2[i]=up[i]=0;
            vis[i]=0;
        }
    }
}

题目二 

1463 -- Strategic game

最小覆盖问题，直接求解

#include<iostream>
#include<cstring>
using namespace std;

const int N=1e5+10,M=N*2;

int h[N],e[M],w[M],ne[M],idx;
bool st[N];
int dp[N][2];
void add(int a, int b){
    e[++idx]=b;ne[idx]=h[a];h[a]=idx;
}

void dfs1(int u, int fa){
    dp[u][0]=0;
    dp[u][1]=1;
    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        if(v==fa)continue;
        dfs1(v,u);
        dp[u][0]+=dp[v][1];
        dp[u][1]+=min(dp[v][1],dp[v][0]);
    }
    h[u]=0;
}
int main(){
   std::ios::sync_with_stdio(false);
cin.tie(0); 
cout.tie(0);
    int n;
    while(cin>>n){
        idx=0;
        for(int i=1; i<=n; i++){
            int fa;
            cin>>fa;
            char c;
            cin>>c>>c;
            int k;
            
            cin>>k>>c;
            //cout<<k<<endl;
            while(k--){
                int a;
                cin>>a;
                add(fa,a);
                add(a,fa);
                st[a]=true;
            }
        }
        int root=0;
        while(st[root])root++;
        //cout<<'a'<<root<<endl;
        dfs1(root,-1);
        cout<<min(dp[root][1],dp[root][0])<<endl;
        for(int i=1; i<=n; i++)st[i]=false;
    }
}

 题目三

[POI2014] FAR-FarmCraft - 洛谷

这道题无非就是贪心+树形dp

我们定义一个状态dp[u]为完成u为根的子树最小的时间；我们可以知道对于u的儿子而言，我们求出了dp[v]，那么如何从dp[v]转移到dp[u]中呢，如何转移是最优解呢?,肯定是当跑完路径v后的时间与最后一个人完成农场的安装时间的差越短越好。那么对于dp[v]中，我们让时间差大的数先执行；

代码如下：注意1号节点也需要玩农场，需要特判

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N=5*1e5+10,M=N*2;

int h[N],e[M],w[M],ne[M],idx;
int  siz[N];
struct node{
    int x,y,z;
    bool operator <(const node& a){
        return z>a.z;
    }
    
}dp[N];
void add(int a, int b){
    e[++idx]=b;ne[idx]=h[a];h[a]=idx;
}

void dfs(int u, int fa){
    siz[u]=1;
    dp[u]={0,w[u],w[u]};
    vector<node>q;
    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        if(v==fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
        q.push_back(dp[v]);
    }
    if(!q.empty() ){
        sort(q.begin(),q.end());
        int maxnum=w[u],times=0;
        for(auto v:q){
            int x=v.x,y=v.y,z=v.z;
            times++;
            maxnum=max(maxnum,times+y);
            times+=(x+1);
        }
        maxnum=u!=1?max(maxnum,times):max(maxnum,times+w[u]);
        dp[u]={times,maxnum,maxnum-times};
    }
    
}
int main(){
   std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)cin>>w[i];
    for(int i=1; i<n; i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1,0);
    cout<<dp[1].y<<endl;
}

 题目四

[CTSC1997] 选课 - 洛谷 

树上背包，枚举每一个状态进行转移即可，使用滚动数组优化

代码如下：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N=310,M=N*2;

int h[N],e[M],w[M],ne[M],idx;
int  dp[N][N];
int siz[N];
void add(int a, int b){
    e[++idx]=b;ne[idx]=h[a];h[a]=idx;
}
int m;
void dfs(int u, int fa){
    siz[u]=1;
    dp[u][1]=w[u];
    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        if(v==fa)continue;
        dfs(v,u);
        for(int j=min(siz[u],m+1); j>=1; j--){
            for(int k=0; k<=siz[v] && k+j<=m+1; k++ ){
                dp[u][j+k]=max(dp[u][j+k],dp[u][j]+dp[v][k]);
            }
        }
        
        siz[u]+=siz[v];
        
    }
    
}
int main(){
   std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    int n;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        int a,b;
        cin>>a>>b;
        add(a,i);
        w[i]=b;
    }
    dfs(0,-1);
    cout<<dp[0][m+1]<<endl;
}

题目五

[POI2008] STA-Station - 洛谷

换根dp转移即可，首先求出f[1]的贡献，转移到子树上

代码如下：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N=1e6+10,M=N*2;
typedef long long LL;
int h[N],e[M],ne[M],idx;
LL  f[N];
int siz[N],dep[N];
void add(int a, int b){
    e[++idx]=b;ne[idx]=h[a];h[a]=idx;
}
LL max_node,maxf;
int n;
void dfs1(int u, int fa){
    dep[u]=dep[fa]+1;
    siz[u]=1;
    
    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        f[u]+=f[v];
    }
    f[u]+=dep[u];
   
}



void dfs2(int u, int fa){

    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        if(v==fa)continue;
        f[v]=f[u]-siz[v]+n-siz[v];
        if(f[v]>maxf){
            maxf=f[v];
            max_node=v;
            //cout<<111<<endl;
        }
        dfs2(v,u);
    }
    
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    cin>>n;
    for(int i=1; i<n; i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs1(1,0);
    max_node=1,maxf=f[1];
   //cout<<maxf<<endl;
    dfs2(1,0);
    cout<<max_node<<endl;
}

题目六 

Tree Painting - CodeForces 1187E - Virtual Judge 

维护siz信息，进行换根dp

代码如下：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N=2*1e5+10,M=N*2;
typedef long long LL;
int h[N],e[M],ne[M],w[M],idx;
LL  f[N];
LL siz[N],val[N];
void add(int a, int b, int c){
    e[++idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx;
}
LL maxf;
int n,num;
void dfs1(int u, int fa){
    siz[u]=1;
    f[u]=0;
    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        int dis=w[i];
        if(v==fa)continue;
        dfs1(v,u);
        f[u]+=f[v];
        siz[u]+=siz[v];
    }
    f[u]+=siz[u];
}



void dfs2(int u, int fa){

    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        int dis=w[i];
        if(v==fa)continue;
        f[v]=f[u]-siz[v]+(num-siz[v]);
        if(f[v]>maxf){
            maxf=f[v];
        }
        dfs2(v,u);
    }
    
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    cin>>n;
    for(int i=1; i<n; i++){
        int a,b;
        cin>>a>>b;
        add(a,b,0);
        add(b,a,0);
    }
    dfs1(1,0);
    num=n;
    maxf=f[1];
   //cout<<maxf<<endl;
    dfs2(1,0);
    cout<<maxf<<endl;
}

题目七 

[USACO10MAR] Great Cow Gathering G - 洛谷 

和上一题差不多，找到转移即可

代码如下：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N=1e5+10,M=N*2;
typedef long long LL;
int h[N],e[M],ne[M],w[M],idx;
LL  f[N];
LL siz[N],val[N];
void add(int a, int b, int c){
    e[++idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx;
}
LL maxf;
int n,num;
void dfs1(int u, int fa){
    siz[u]=val[u];
    f[u]=0;
    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        int dis=w[i];
        if(v==fa)continue;
        dfs1(v,u);
        f[u]+=siz[v]*dis+f[v];
        siz[u]+=siz[v];
    }
   
}



void dfs2(int u, int fa){

    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        int dis=w[i];
        if(v==fa)continue;
        f[v]=f[u]-siz[v]*dis+(num-siz[v])*dis;
        if(f[v]<maxf){
            maxf=f[v];
        }
        dfs2(v,u);
    }
    
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++)cin>>val[i];
    for(int i=1; i<n; i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs1(1,0);
    num=siz[1];
    maxf=f[1];
   //cout<<maxf<<endl;
    dfs2(1,0);
    cout<<maxf<<endl;
}

题目八 

 Accumulation Degree - 洛谷

一开始以为是网络流的问题，但是仔细一看，这个转移的条件很弱，可以看到求出u的ans，可以推出v的ans转移方程f[v]=f[v]+min(w,f[u]-min(w,f[v]));大致意思就是v流出是合法的子树f[v]+从上面流出的值(取决于边的容量，以及u需要的多少)

代码如下：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N=2*1e5+10,M=N*2,INF=1e9;
typedef long long LL;
int h[N],e[M],ne[M],w[M],idx;
LL  f[N];
LL siz[N],val[N];
void add(int a, int b, int c){
    e[++idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx;
}
LL maxf;
int n,num;
void dfs1(int u, int fa){
    f[u]=0;
    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        LL dis=w[i];
        if(v==fa)continue;
        dfs1(v,u);
        if(f[v]!=0)
        f[u]+=min(dis,f[v]);
        else f[u]+=dis;
    }
}



void dfs2(int u, int fa){

    for(int i=h[u]; i; i=ne[i]){
        int v=e[i];
        LL dis=w[i];
        if(v==fa)continue;
        f[v]=f[v]+min(dis,f[u]-min(dis,f[v]));
        if(f[v]>maxf){
            maxf=f[v];
        }
        dfs2(v,u);
    }
    h[u]=0;
    
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        idx=0;
        cin>>n;
        for(int i=1; i<n; i++){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
            add(b,a,c);
        }
        dfs1(1,0);
        maxf=f[1];
        dfs2(1,0);
        cout<<maxf<<endl;
    }
}

标签：idx,int,siz,ne,fa,树形,做题,include,DP
From： https://blog.csdn.net/2403_86761086/article/details/142108911

相关文章

  • 虚树+树形dp
    虚树实际上是一颗浓缩子树；使用虚树的题目大部分具有查询的点有限，同时虚树构建的信息符合规则；做虚树的题目：步骤为先想出原树的暴力求解做法，然后构建虚树同时向其中添加有用信息（比如边权）；虚树的构建过程：虚树的构建大致有两种，但是两种方式都与dfs序有关；首先解释为什么与dfs序有......
  • 九月做题记录
    都成老年选手了，能记点就记点吧。9.10BZOJ3786星际探索不知道为啥瞥见了这题题解，所以成了个玛丽题，跑出括号序后成区间问题，平衡树维护区间移动，加法。对于移动一段区间，平衡树需要维护节点内正的贡献数量，方便区间加法，然后区间移动的变化量要算清。点击查看代码#include<bits/s......
  • 线性dp：LeetCode122.买卖股票的最佳时机ll
    买卖股票本文所讲解的内容与LeetCode122.买卖股票的最佳时机ll，这道题题意相同，阅读完本文后可以自行挑战一下力扣链接题目叙述：给定一个长度为N的数组，数组中的第i个数字表示一个给定股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交......
  • Wordpress采集发布插件-免费下载
    推荐一款可以自动采集文章数据，并发布到Wordpress网站的Wordpress采集发布插件，支持对接简数采集器，火车头采集器，八爪鱼采集器，后羿采集器等大多数网页文章数据采集软件。Wordpress采集发布插件使用方法如下：1. 下载并安装Wordpress采集发布插件1.1 Wordpress采集发布插件免费下载......
  • DP
    动态规划动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。三个条件：最优子结构，无后效性和子问题重叠。最优子结构证明问题最优解的第一个组成部分是做出一个选择；对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解......
  • [DPDK] dumpcap报错EAL init failed: is primary process running?解决办法
    [DPDK]dumpcap报错EALinitfailed:isprimaryprocessrunning?解决办法问题我写了一个DPDK程序，现在想要用DPDK自带的dpdk-dumpcap工具来抓包测试。根据官网描述，我们需要先启动我们的程序为主进程，然后启动dpdk-dumpcap为副进程。但是我直接运行dpdk-dumpcap，显示如下错误：注：......
  • TCP和UDP对比
    TCP和UDP对比TCP（TransmissionControlProtocol，传输控制协议）和UDP（UserDatagramProtocol，用户数据报协议）是两种常用的网络传输层协议，它们在网络通信中扮演着重要的角色。以下是它们的主要区别：连接性：TCP：TCP是一种面向连接的协议，在数据传输之前需要建立一个连接（三次握手），数据......
  • TCP和UDP
    TCP（TransmissionControlProtocol，传输控制协议）和UDP（UserDatagramProtocol，用户数据报协议）是两种常用的网络传输层协议，它们在网络通信中扮演着重要的角色。以下是它们的主要区别：连接性：TCP：是一种面向连接的协议。在数据传输开始之前，必须建立一个连接，通过三次握手过程来确保......
  • el-table树形懒加载表格展开后 子节点修改数据后实时刷新
    问题描述在项目中遇到一个关于el-table的懒加载树型结构修改数据后需要刷新数据的问题，需要手动刷新页面之后才能刷新问题解决：1.首先创建map来用于存取数据，constloadMap=newMap();//存储load加载的子节点以能够编辑后更新2.在table展开子节点时，用map存下每次被加载......
  • NPDP和PMP有啥区别？其实就这个3点
    1、发证机构不同PMP是由项目管理协会PMI发起，严格评估项目管理人员知识技能是否具有高品质的资格认证考试。1999年，中国国际人才交流基金会将项目管理协会制定的《项目管理知识体系指南》和“项目管理专业人士职业资格认证”引入中国。NPDP是由美国产品开发与管理协会PDMA......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99