首页 > 其他分享 >树形dp真的是太有意思啦!

树形dp真的是太有意思啦!

时间:2022-11-09 18:11:57浏览次数:45  
标签:有意思 le int max 树形 maxn siz 节点 dp

P3047 [USACO12FEB]Nearby Cows G

题意:

给你一棵 \(n\) 个点的树,点带权,对于每个节点求出距离它不超过 \(k\) 的所有节点权值和 \(m_i\)。

\(1\le n\le 1e5,1\le k\le 20 ,0\le c_i \le 1e3\)

解题思路:

一眼换根 \(\operatorname{dp}\)。问题是该如何设状态。

考虑设 \(f_{u,j}\) 为所有距离 \(u\) 节点 \(j\) 长度的权值和,对于第一次 \(\operatorname{dfs}\),显然应该如下转移:

\[f_{u,j}=\sum_{v\in son_u}f_{v,j-1} \]

(子树中距离 \(v\) 节点 \(j-1\) 长度的点即为距离 \(u\) 节点 \(j\) 长度的点)

对于第二次 \(\operatorname{dfs}\),我们已经知道了对于每个节点子树中的贡献,接下来应该计算子树之外的贡献。因此对于节点 \(u\),应该将子树中包含 \(v\) 节点的贡献减去,然后再让 \(v\) 节点加上此时 \(u\) 的其他子树和父亲的贡献,得到的就是最终答案。注意这某一子树搜索完之后要将 \(f_u\) 的状态恢复。

转移式为:

\[f_{u,j}=f_{u,j}-f_{v,j-1} \\ f_{v,j}=f_{v,j}+f_{u,j-1} \]

对于每个节点 \(u\), 答案为 \(\sum_{j=0}^{k}f_{u,j}\)。

代码:

code
#include <cstdio>
#include <algorithm>
#define Reg register
#define ll long long
using namespace std;
const int maxn=101000;
int n,K,cnt,head[maxn],a[maxn];
int dep[maxn],ans[maxn];
int f[maxn][30];
struct ED{
    int nxt,to;
}e[maxn<<1];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }
    return s*w;
}
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
inline void dfs(int u,int fa){
    f[u][0]=a[u]; 
    for(Reg int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        for(Reg int j=K;j>=1;j--) f[u][j]+=f[v][j-1];
    }
}
inline void dfs_2(int u,int fa){
    for(Reg int i=0;i<=K;++i) ans[u]+=f[u][i];
    for(Reg int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        for(Reg int j=K;j>=1;j--) f[u][j]-=f[v][j-1];
        for(Reg int j=K;j>=1;j--) f[v][j]+=f[u][j-1];
        dfs_2(v,u);
        for(Reg int j=K;j>=1;j--) f[v][j]-=f[u][j-1];
        for(Reg int j=K;j>=1;j--) f[u][j]+=f[v][j-1];
    }
}
int main(){
    n=read(),K=read();
    for(Reg int i=1;i<=n-1;++i){
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    for(Reg int i=1;i<=n;++i) a[i]=read();
    dfs(1,0),dfs_2(1,0);
    for(Reg int i=1;i<=n;++i) printf("%d\n",ans[i]);    
    return 0;
}







P1272 重建道路

题意:

给定一棵 \(n\) 个节点的树,询问使包含 \(P\) 个节点的连通块与这棵树分离所需要砍掉的最小边数。

$1\le n\le 150,1\le P\le n $

解题思路:

设计状态是关键...不然就会像某人一样死活调不出来,连自己假没假都不知道。

设 \(f_{u,t}\) 为在 \(u\) 节点的子树中砍掉 \(t\) 个节点所需砍掉的最小边数,易知当 \(u\) 不为根节点时 \(f_{u,siz_u}=1\),以及任意情况下都有 \(f_{u,0}=0\)。其他初始化为 \(inf\)。

接下来思考如何转移以及计算答案。

转移比较好说,是一般树形背包的套路,即:

\[f_{u,t}=\min(f_{u,t},f_{u,t-j}+f_{v,j}) \]

计算答案则是:

\[ans=\min(ans,f_{u,siz_u-P}+f_{u,siz_u}) \]

(即砍掉子树中的一些点再分离出来整棵子树)

代码:

code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Reg register
#define ll long long
using namespace std;
const int maxn=210,inf=2147483100;
int n,K,cnt,ans=inf,siz[maxn],head[maxn];
int f[maxn][maxn];
struct ED{
    int to,nxt;
}e[maxn<<1];
//定义状态很重要
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }
    return s*w;
}
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
inline void dfso(int u){
    siz[u]=1;
    for(Reg int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        //printf("%d %d\n",u,v);
        dfso(v);
        siz[u]+=siz[v];
    }
    f[u][siz[u]]=1;
    f[u][0]=0;
}
inline void dfst(int u){
   // printf("%d\n",u);
    for(Reg int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        //printf("%d %d\n",u,v);
        dfst(v);
        for(Reg int t=siz[u]-1;t;--t)
            for(Reg int k=0;k<=t;++k)
                f[u][t]=min(f[u][t],f[u][t-k]+f[v][k]);
    }
    if(siz[u]>=K) ans=min(ans,f[u][siz[u]-K]+f[u][siz[u]]);
}
int main(){
    n=read(),K=read();
    //printf("1\n");
    for(Reg int i=1;i<n;++i){
        int x=read(),y=read();
        add(x,y);
    }
    //printf("1\n");
    memset(f,0x3f,sizeof(f));
    //memset(minn,0x3f,sizeof(minn));
    dfso(1);
    f[1][siz[1]]=0;
    dfst(1);
    printf("%d\n",ans);
    return 0;
}






P3761 [TJOI2017]城市

题意:

给定一棵 \(n\) 个节点的树,边带权,可以断开一条边再在另外一个位置连上一条边权相同的边(依然要保证是棵树),求进行一次操作后两个节点最大距离的最小值。

$1\le n\le 5e3 $

解题思路:

盲猜有人想用二分

事实上二分根本不可写。

发现断开的这一条边一定会是直径上的边,否则距离最大的依然会是直径。

继续发现断开某一条边后树会分为两个连通块,再连边肯定是于两个联通块之间连边。

枚举直径上的一条边 \((u,v,w)\) ,考虑答案如何被更新:

  1. \(u\) 所在连通块的两点之间最大距离。

  2. \(v\) 所在连通块的两点之间最大距离。

  3. 块内所有点关于 \(x\) 的最大距离加上块内所有点关于 \(y\) 的最大距离加上 \(w\)。

(其中 \(x\) 属于 \(u\) 所在的连通块,\(y\) 属于 \(v\) 所在的连通块,枚举可得)

三者取 \(\max\) ,再对 \(ans\) 取 \(\min\) 即可。

好,发现可以无脑树剖搞了,这样的复杂度大概为 \(O(n^3 \log^2 n)\),可以拿到 \(\operatorname{30pts}\)。

能不能再给力一点儿?

好像意识到了什么。

\(u\) 所在连通块的两点之间最大距离。

\(v\) 所在连通块的两点之间最大距离。

显然是树的直径。

块内所有点关于 \(x\) 的最大距离加上块内所有点关于 \(y\) 的最大距离加上 \(w\)。

因为要使答案最小,而且两个连通块选什么点互不影响,我们分明可以选择对块内所有点最大距离最小的 \(x\) 和 \(y\) 。这需要知道每个 \(x\) 或者 \(y\) 对块内所有点的最大距离。

考虑换根 \(\operatorname{dp}\) 。

首先对每个连通块进行第一次 \(\operatorname{dfs}\) 以求出子树内叶节点与该节点的最大距离 \(f_{u,0}\) ,以及树的直径。

对于第二次 \(\operatorname{dfs}\),对于某个节点的贡献是子树以内的最长链或者是子树以外的最长链。 其中子树以内的最长链已经求出。设 \(d_u\) 为 \(u\) 节点子树以外的最长链,那么转移应该为:

\[d_v=\max(d_v,\max(d_u,f_{u,0})) \]

但是当 \(v\) 本身属于最长链时上述方程不成立,因此还要在第一次的 \(\operatorname{dfs}\) 维护一个子树内次长链 \(f_{u,1}\) ,并记录最长链对应的节点 \(fir_u\)。最终的转移为:

\[d_v= \begin {cases} \max(d_v,\max(d_u,f_{u,0})) \ \ \ \ \ \ \ \ \ \ \ \ (v=fir_u) \\ \max(d_v,\max(d_u,f_{u,1})) \ \ \ \ \ \ \ \ \ \ \ \ (v\ne fir_u) \end{cases} \]

取 $\min $ 可得合法的 \(x,y\) 。

设两个连通块直径取 \(\max\) 后的结果为 \(res\),那么答案为:

\[ans=\min(ans,\max(res,d_x+d_y+w)) \]

代码:

code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Reg register
#define ll long long
using namespace std;
const int maxn=5005,inf=2147483100;
int n,cnt,lroot,rroot,maxx,ans;
int head[maxn],vis[maxn],dismax[maxn],dissec[maxn],fir[maxn],sec[maxn];
int evis[maxn],dis[maxn],pvis[maxn];
struct ED{
    int to,nxt,w;
}e[maxn<<1];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }
    return s*w;
}
inline void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
inline void dfs(int u,int fa,int depth){
    if(depth>maxx) ans=maxx=depth,rroot=u;
    for(Reg int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u,depth+e[i].w);
    }
}
int res=0,minu=inf,minv=inf;
inline void fdfs(int u,int fa){
    for(Reg int i=head[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].w;
        if(evis[i+1>>1]) continue;
        if(v==fa) continue;
        fdfs(v,u);
        res=max(res,dismax[u]+dismax[v]+w);
        if(dismax[v]+w>dismax[u]){
            dissec[u]=dismax[u];
            sec[u]=fir[u];
            dismax[u]=dismax[v]+w;
            fir[u]=v;
        }else if(dismax[v]+w>dissec[u]){
            dissec[u]=dismax[v]+w;
            sec[u]=v;
        }
    }
}
inline void pdfs(int u,int fa,int idx,int S){
    if(!idx) minu=min(minu,max(dismax[u],S));
    else minv=min(minv,max(dismax[u],S));
    for(Reg int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(evis[i+1>>1]) continue;
        if(v==fa) continue;
        if(v==fir[u]){
            if(sec[u])pdfs(v,u,idx,max(S,dissec[u])+e[i].w);
            else pdfs(v,u,idx,S+e[i].w);
        }
        else pdfs(v,u,idx,max(S,dismax[u])+e[i].w);
    }
}
inline void solve(int u,int v,int x){
    res=0,minu=inf,minv=inf;
    memset(fir,0,sizeof(int)*(n+10));
    memset(sec,0,sizeof(int)*(n+10));
    memset(dismax,0,sizeof(int)*(n+10));
    memset(dissec,0,sizeof(int)*(n+10));
    fdfs(u,0);pdfs(u,0,0,0);
    fdfs(v,0);pdfs(v,0,1,0);
    ans=min(ans,max(res,x+minu+minv));
}
inline void finds(int u,int fa){
    if(u==rroot) vis[u]=1; 
    for(Reg int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        finds(v,u);
        if(vis[v]){
            evis[i+1>>1]=1;
            solve(u,v,e[i].w);
            vis[u]=1;
            evis[i+1>>1]=0;
        } 
    }
}
int main(){
    n=read();
    for(Reg int i=1;i<n;++i){
        int x=read(),y=read(),w=read();
        add(x,y,w),add(y,x,w);
    }
    dfs(1,0,0);lroot=rroot,maxx=0;
    dfs(lroot,0,0);
    //printf("%d %d\n",lroot,rroot);
    finds(lroot,0);
    printf("%d\n",ans);
    return 0;
}






CF708C Centroids

题意:

给定一颗树,你有一次将树改造的机会,改造的意思是删去一条边,再加入一条边,保证改造后还是一棵树。

请问有多少点可以通过改造,成为这颗树的重心?(如果以某个点为根,每个子树的大小都不大于\(\lfloor \frac{n}{2} \rfloor\),则称某个点为重心)

\(n\le 4e5\)

解题思路:

一眼换根 \(\operatorname{dp}\)。

能推出来对于某个点若不满足重心的要求,可以将其一个大小大于 \(\lfloor \frac{n}{2} \rfloor\) 的子树切下一个最大的小于等于 \(\lfloor \frac{n}{2} \rfloor\) 的部分接到根上。

然后发现不会设状态,颓了眼题解,于是对 \(\operatorname{BE}\) 是神必这件事深以为然。

设 \(f_u\) 为子树内最大的小于等于 \(\lfloor \frac{n}{2} \rfloor\) 的部分,转移如下:

\[f_u= \begin {cases} \max(f_u,siz_v) \ \ \ \ \ \ \ \ \ (siz_v \le \lfloor \frac{n}{2} \rfloor) \\ \max(f_u,f_v) \ \ \ \ \ \ \ \ \ \ \ \ (siz_v > \lfloor \frac{n}{2} \rfloor) \end{cases} \]

(比较显然)

但是要求换根。

那么就需要跟上一道题一样,要维护最大值和次大值了(转移方程不写力)。

如果说这个节点本来就是重心那么它可以被改造成重心(废话),否则必须满足如下要求:

\[(maxsiz_u-f_u \le \lfloor \frac{n}{2} \rfloor) \]

当然 \(maxsiz_u\) 可以是父节点的那一部分 ( \(n-siz_u\) )。

然后就做完了。

代码:

code
#include <cstdio>
#include <algorithm>
#define Reg register
using namespace std;
const int maxn=410000;
int n,cnt,head[maxn],siz[maxn],fir[maxn],sec[maxn],maxsiz[maxn];
int vis[maxn],f[maxn][2],dp[maxn];
struct ED{
    int to,nxt;
}e[maxn<<1];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }
    return s*w;
}
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
inline void dfso(int u,int fa){
    siz[u]=1;
    for(Reg int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfso(v,u);
        maxsiz[u]=max(maxsiz[u],siz[v]);
        if(siz[v]<=n/2){
            if(siz[v]>f[u][0]){
                f[u][1]=f[u][0],sec[u]=fir[u];
                f[u][0]=siz[v],fir[u]=v;
            }else if(siz[v]>f[u][1]){
                f[u][1]=siz[v],sec[u]=v;
            }
        }else{
            if(f[v][0]>f[u][0]){
                f[u][1]=f[u][0],sec[u]=fir[u];
                f[u][0]=f[v][0],fir[u]=v;
            }else if(f[v][0]>f[u][1]){
                f[u][1]=f[v][0],sec[u]=v;
            }
        }
        siz[u]+=siz[v];
    }
  //  printf("%d %d\n",f[u][0],f[u][1]);
}
inline void dfst(int u,int fa){
    vis[u]=1;
    if(maxsiz[u]>n/2) vis[u]=((maxsiz[u]-f[u][0])<=n/2);
    else if(n-siz[u]>n/2) vis[u]=((n-siz[u]-dp[u])<=n/2);
    for(Reg int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        if(n-siz[v]<=n/2) dp[v]=max(dp[v],n-siz[v]);
        else dp[v]=max(dp[v],dp[u]);
        if(v==fir[u]){
            if(sec[u]) dp[v]=max(dp[v],f[u][1]); 
            dfst(v,u);
        }else{
            dp[v]=max(dp[v],f[u][0]);
            dfst(v,u);
        }
    }
}
int main(){
    n=read();
    for(Reg int i=1;i<n;++i){
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    dfso(1,0),dfst(1,0);
    for(Reg int i=1;i<=n;++i) printf("%d ",vis[i]);
    printf("\n");
    return 0;
}

累麻。

标签:有意思,le,int,max,树形,maxn,siz,节点,dp
From: https://www.cnblogs.com/Broken-Eclipse/p/16874286.html

相关文章

  • EXPDP IMPDB ATTACH
    可以使用kill_job或stop_job结束或停止Job,stop的job可以继续,kill的不行。 MicrosoftWindows[版本6.1.7601]版权所有(c)2009MicrosoftCorporation。保留所有......
  • 将数组数据转化成树形结构 tranListToTreeData
    exportfunctiontranListToTreeData(list,rootValue){//list是最完整的数组letarr=[];//记录儿子list.forEach((item)=>{//记录是否有儿子......
  • 并行训练算法一锅炖: DDP, TP, PP, ZeRO
    本文主要参考ColossalAI论文Colossal-AI:AUnifiedDeepLearningSystemForLarge-ScaleParallelTrainingColossalAI框架开源提供了本文介绍的所有并行训练:https......
  • Digit Dp
    数位dp总结值域巨大的题目,考虑分治、矩乘、数位dp和规律。数位dp通常需要将对数的描述转化成对每个数位的描述,从而按位dp,尤其是等式。关于不等式的刻画,通......
  • CS Academy Telegraph 题解 (分层DP)
    CSAcademy是一个比较小众的罗马尼亚OJ,UI好看功能多样,但是需要fq才能注册。访问是不用fq的常用工具:画图找不同题目链接前段时间刚做过类似的分层dp题,这次又忘了,深刻反......
  • Linux高并发网络编程开发——epoll-udp
    在学习Linux高并发网络编程开发总结了笔记,并分享出来。10-Linux系统编程-第13天(epoll-udp)目录:一、学习目标二、复习1、通过gdb定位段错误的位置2、TCP状态转换复习三、epoll......
  • Antd Tree树形控件 自定义插槽
    使用titleRender属性自定义节点渲染函数,不需要处理树型数据,达到比如右侧新增按钮的需求(如图三)<Tree ... titleRender={(nodeData)=>{return(......
  • ODPS基本概念
    什么是ODPS?开发数据处理服务(OpenDataProcessingService,简称ODPS),2016年后更名MaxComputer。ODPS是一种由阿里云自主研发,针对TB/PB级数据、实时性要求不高的分布式处理服......
  • dpkg 安装mysql
    名称版本系统Ubuntu16.04MySQL5.7.26下载安装包wgethttps://dev.mysql.com/get/Downloads/MySQL-8.mysql-server_8.0.16-2ubuntu18.04_amd64.deb-bun......
  • 2022NewStarCTF新生赛一些比较有意思的题目wp
    Misc_蚁剑流量分析Pcap的文件可以直接使用工具 编辑器打开目录,一个一个看,可以找到eval危险函数 看到n3wst4r,直接使用linux正则匹配,找出相关内容Url解码,了解一下蚁......