树形DP(模板+题目合集)

做了好几天的树形DP的题,没做那种特别难的,感觉类型都差不多,大同小异吧

参考OI WiKi

首先是经典的树形DP题目

洛谷P1352 没有上司的舞会

题目链接:https://www.luogu.com.cn/problem/P1352

某大学有 n个职员,编号为 1~n 。他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数  ,但是呢,如果某个职员的上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数是多少。

可以定义 f[i][0] 表示标号为i的人不去 和 f[i][1] 表示编号为i的人去 时的最优解

转移方程( v 表示 i 节点的子节点)

f[i][0]+ = max(f[v][1] , f[v][0])

f[i][1]+ = f[v][0]

代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    int next,to;
}q[6005];
int f[6005][3],head[10000],book[6005],v[6005];
void dfs(int n)
{
    v[n]=1;
    for(int j=head[n];j!=-1;j=q[j].next)
    {
        if(v[q[j].to]==1)
        {continue;}
        dfs(q[j].to);
        f[n][1]+=f[q[j].to][0];
        f[n][0]+=max(f[q[j].to][1],f[q[j].to][0]);
    }
    return;
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,l,k;
    cin>>n;
    for(int i=1;i<=n;i++)
    {cin>>f[i][1];}
    for(int i=1;i<=n;i++)
    {
        cin>>l>>k;
        q[i].to=l;
        q[i].next=head[k];
        head[k]=i;
        book[l]=1;
    }
    int u;
    for(int i=1;i<=n;i++)
    {
        if(book[i]==0)
        {u=i;dfs(i);break;}
    }
    cout<<max(f[u][1],f[u][0])<<endl;
    return 0;
}

Hdu 2196 Computer

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2196

求树中最长路径

就是对于每个点而言,求出离这个点最远距离的点的距离是多少

PS(因为没看到多组输入WA10多次。。。唉)

做的很多树形DP的题目大都是无根树,即每个点都可以做根

链式前向星存双向边

一般都是先选取一个点做根进行DP,再换根DP,两次dfs

这个题大概也是这个思想吧

对于一个节点,最远距离可能在该节点的子树方向上,也可能在该节点的父节点方向上,两次dfs,第一次求出该节点子树方向上最长距离,第二次求父亲节点方向上的

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MaxSize = 10005;
struct node
{
    ll w,to,next;
}q[10005];
ll head[MaxSize],d[MaxSize][3],idx[MaxSize];
void dfs1(ll n)
{
    ll st[10005],j=0;
    for(int i=head[n];i!=-1;i=q[i].next)
    {
        dfs1(q[i].to);
        d[n][0]=max(d[n][0],d[q[i].to][0]+q[i].w);
        st[j++]=d[q[i].to][0]+q[i].w;
    }
    sort(st,st+j);
    if(j>1)
    {d[n][1]=st[j-2];}
    return ;
}
void dfs2(ll n,ll f,ll w)
{
    if(n!=f)
    {
        ll op=d[n][0]+w;
        if(op==d[f][0])
        {
            d[n][2]=max(d[n][2],d[f][2]+w);
            d[n][2]=max(d[n][2],d[f][1]+w);
        }
        else
        {
            d[n][2]=max(d[n][2],d[f][2]+w);
            d[n][2]=max(d[n][2],d[f][0]+w);
        }
    }
    for(int i=head[n];i!=-1;i=q[i].next)
    {
        dfs2(q[i].to,n,q[i].w);
    }
    return ;
}
int main()
{
    ll n,a,b;
    while(~scanf("%lld",&n)){
    memset(head,-1,sizeof(head));
    memset(d,0,sizeof(d));
    ll cnt=1;
    for(int i=2;i<=n;i++)
    {
        scanf("%lld %lld",&a,&b);
        q[cnt].to=i;
        q[cnt].w=b;
        q[cnt].next=head[a];
        head[a]=cnt;
        cnt++;
    }
    dfs1(1);
    dfs2(1,1,0);
    for(int i=1;i<=n;i++)
    {
        cout<<max(d[i][0],d[i][2])<<endl;
    }
    }
    return 0;
}

Codeforces#627 div.3 F.Maximum White Subtree

也是给你一棵树,树中每个点是白色或黑色,问对于每个点,在包含该点的连通块中白色点数量 - 黑色点数量 最大是多少?

两次dfs,第一次求点的子节点连通方向,第二次换根求父节点方向

代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MaxSize = 200005;
struct node
{
    int to,next;
}q[3*MaxSize];
int a[MaxSize],head[MaxSize],cnt=1,d[MaxSize];
void add(int a,int b)
{
    q[cnt].to=a;
    q[cnt].next=head[b];
    head[b]=cnt;
    cnt++;
}
void dfs(int u,int f)
{
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(v==f)
        {continue;}
        dfs(v,u);
        d[u]=max(d[u],d[v]+d[u]);
    }
    return ;
}
void dfs2(int u,int f)
{
    if(u!=f)
    {
        if(d[u]>=0)
        {d[u]=max(d[u],d[f]);}
        else
        {d[u]=max(d[u],d[u]+d[f]);}
    }
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(v==f)
        {continue;}
        dfs2(q[i].to,u);
    }
    return;
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==0)d[i]=-1;
        else{d[i]=1;}
    }
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d %d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,1);
    dfs2(1,1);
    for(int i=1;i<=n;i++)
    {
        cout<<d[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Poj 1463 Strategic game

最小点覆盖问题(这道题其实是覆盖边)

每个点都可以覆盖其周围的边,求覆盖所有边的最小点数

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
struct node
{
    int to,next;
}q[4000];
int head[4000],cnt=1,d[1800][3];
void add(int a,int b)
{
    q[cnt].to=b;
    q[cnt].next=head[a];
    head[a]=cnt++;
}
void dfs(int u,int f)
{
    int cc=0;
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        if(q[i].to==f)
        {continue;}
        cc++;
    }
    if(cc==0){return;}
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(v==f){continue;}
        dfs(v,u);
        if(d[v][1]==0)
        {d[u][1]=1;}
    }
    return;
}
int main()
{
    int n,c,p,o;
    while(scanf("%d",&n)!=EOF){
    memset(head,-1,sizeof(head));
    memset(d,0,sizeof(d));
    cnt=1;
    for(int k=0;k<n;k++){
    scanf("%d",&o);
    scanf(":(%d)",&c);
    for(int i=1;i<=c;i++)
    {
        scanf("%d",&p);
        add(p,o);add(o,p);
    }}
    dfs(0,0);
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(d[i][1]==1)
        {ans++;}
    }
    printf("%d\n",ans);
    }
    return 0;
}

Poj 3585 Accumulation Degree

最大流

老套路,两次扫描即可

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
using namespace std;
const int Size = 200005;
struct node
{
    int to,w,next;
}q[2*Size];
int head[Size],d[Size],book[Size],cnt;
void add(int a,int b,int c)
{
    q[cnt].to=b;
    q[cnt].w=c;
    q[cnt].next=head[a];
    head[a]=cnt++;
}
void dfs(int u,int f)
{
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(v==f)
        {continue;}
        dfs(v,u);
        if(book[v]==1)
        {d[u]+=q[i].w;}
        else
        {
            if(q[i].w>=d[v])
            {d[u]+=d[v];}
            else
            {d[u]+=q[i].w;}
        }
    }
    return;
}
void dfs2(int u,int f,int w)
{
    if(u!=f)
    {
        int op;
        if(book[f]==1)
        {op=d[f];}
        else
        {op=d[f]-min(d[u],w);}
        d[u]+=min(op,w);
    }
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(v==f){continue;}
        dfs2(v,u,q[i].w);
    }
    return ;
}
int main()
{
    int t,n,a,b,c;
    scanf("%d",&t);
    while(t--)
    {
        memset(head,-1,sizeof(head));
        memset(d,0,sizeof(d));
        memset(book,0,sizeof(book));
        cnt=1;
        scanf("%d",&n);
        for(int i=1;i<=n-1;i++)
        {
            scanf("%d %d %d",&a,&b,&c);
            book[a]++;book[b]++;
            add(a,b,c);add(b,a,c);
        }
        dfs(1,1);
        dfs2(1,1,0);
        int ans=-1;
        for(int i=1;i<=n;i++)
        {ans=max(ans,d[i]);}
        printf("%d\n",ans);
    }
    return 0;
}

洛谷P1273 有线电视网

树上分组背包

代码:

#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
    x=0; register char c=getchar(); register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
int n,m,cnt=0,k,a,c;
struct node
{
    int to,next,w;
}e[50005];
int head[50005],num[50005];
int d[3005][3005];
void add(int u,int v,int w)
{
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;
}
void dfs(int u,int fa,int w)
{
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        dfs(v,u,w+e[i].w);
        num[u]+=num[v];
    }
    if(u>=n-m+1){d[u][1]=d[u][1]-w;return;}
    for(int i=head[u];i!=-1;i=e[i].next)//枚举组
    {
        int v=e[i].to;
        for(int j=num[u];j>=0;j--)//枚举背包容量
        {
            for(int k=1;k<=num[v];k++)
            {
                if(j>=k){
                    d[u][j]=max(d[u][j],d[u][j-k]+d[v][k]+w);
                }
            }
        }
    }
    for(int j=num[u];j>=1;j--)
    {d[u][j]-=w;}
}
int main()
{
    IOS
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=n+2;i++){for(int j=1;j<=n+2;j++){d[i][j]=-9999999;}}
    for(int i=1;i<=n-m;i++)
    {
        cin>>k;
        for(int j=1;j<=k;j++)
        {cin>>a>>c;
        add(i,a,c);}
    }
    for(int i=n-m+1;i<=n;i++)
    {cin>>d[i][1];num[i]=1;}
    dfs(1,1,0);
    int ans=0;
    for(int i=0;i<=n;i++)
    {
        //cout<<d[1][i]<<endl;
        if(d[1][i]>=0){ans=i;}
    }
    cout<<ans<<endl;
    return 0;
}

洛谷 P2585 [ZJOI2006]三色二叉树

两次dfs

代码:

#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
string s;
int pos,u=1;
struct node
{
    int val,l,r;
}e[600005];
int d[600005][5];
int ff[600005][5];
void build()
{
    int now=u;
    if(s[pos]=='2')
    {
        e[now].l=u+1;
        pos++;u++;build();
        e[now].r=u+1;
        pos++;u++;build();
    }
    else if(s[pos]=='1')
    {
        e[u].l=u+1;
        pos++;u++;build();
    }
    else
    {return;}
}
void dfs(int u,int f)
{
    int op1=e[u].l;
    int op2=e[u].r;
    if(op1==0)
    {
        d[u][1]=1;
        return;
    }
    if(op2==0)
    {
        dfs(op1,u);
        d[u][1]=d[op1][0]+1;
        d[u][0]=d[op1][1];
        return;
    }
    if(op1!=0&&op2!=0)
    {
        dfs(op1,u);
        dfs(op2,u);
        d[u][1]=d[op1][0]+d[op2][0]+1;
        d[u][0]=max(d[op1][1]+d[op2][0],d[op1][0]+d[op2][1]);
        return;
    }
}
void dfs2(int u,int f)
{
    int op1=e[u].l;
    int op2=e[u].r;
    if(op1==0)
    {
        ff[u][1]=1;
        return;
    }
    if(op2==0)
    {
        dfs2(op1,u);
        ff[u][1]=ff[op1][0]+1;
        ff[u][0]=min(ff[op1][1],ff[op1][0]);
        return;
    }
    if(op1!=0&&op2!=0)
    {
        dfs2(op1,u);
        dfs2(op2,u);
        ff[u][1]=ff[op1][0]+ff[op2][0]+1;
        ff[u][0]=min(ff[op1][1]+ff[op2][0],ff[op1][0]+ff[op2][1]);
        return;
    }
}
int main()
{
	cin>>s;
	int n=s.size();
	build();
	dfs(1,1);
	dfs2(1,1);
	cout<<max(d[1][1],d[1][0])<<" ";
	cout<<min(ff[1][1],ff[1][0])<<endl;
    return 0;
}

Codeforces#688 div2 E. Dog Snacks

仔细思考一下当前节点与子节点的关系

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while (c < '0' || c > '9') {if (c == '-')f = -1; c = getchar();}
    while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
using namespace std;
int t,n,ans;
int exd,now;
struct node
{
    int to,next;
}e[400005];
int head[400005],cnt;
void add(int u,int v)
{
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt++;
}
int d[200005];
int num[200005];
void dfs(int u,int fa)
{
    bool flag=0;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa){continue;}
        flag=1;
        dfs(v,u);
        d[u]=min(d[u],d[v]+1);
        if(u==1)
        {
            if(d[v]+1>now)
            {now=d[v]+1;
            exd=0;}
            else if(d[v]+1==now)
            {exd=1;}
        }
        else
        {
            if(num[u]==1){continue;}
            else{ans=max(ans,d[v]+2);}
        }
    }
    if(!flag){d[u]=0;}
}
void dfs_pre(int u,int fa)
{
    num[u]=0;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa){continue;}
        num[u]++;
    }
}
int main()
{
    cin>>t;
    while(t--)
    {
        ans=1;now=1;exd=0;
        cin>>n;
        for(int i=0;i<=2*n+2;i++){head[i]=-1;}cnt=0;
        for(int i=1;i<=n;i++){d[i]=9999999;}
        for(int i=1;i<=n-1;i++)
        {
            int x,y;
            cin>>x>>y;
            add(x,y);
            add(y,x);
        }
        if(n==2){cout<<"1"<<endl;continue;}
        dfs_pre(1,1);
        dfs(1,1);
        cout<<max(ans,now+exd)<<endl;
    }
    return 0;
} 

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注