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

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

时间：2022-11-09 18:11:57浏览次数：40  
标签：有意思 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解码，了解一下蚁......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99