树形DP()

这篇具有很好参考价值的文章主要介绍了树形DP()。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

没有上司的舞会

Ural 大学有 N 名职员,编号为 1∼N。

他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。

每个职员有一个快乐指数,用整数 Hi 给出,其中 1≤i≤N。

现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。

在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。

输入格式

第一行一个整数 N。

接下来 N 行,第 i 行表示 i 号职员的快乐指数 Hi。

接下来 N−1 行,每行输入一对整数 L,K,表示 K 是 L 的直接上司。(注意一下,后一个数是前一个数的父节点,不要搞反)。

输出格式

输出最大的快乐指数。

数据范围

1≤N≤6000
−128≤Hi≤127

输入样例:

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例:

5

树形DP(),DP,算法,dp

 树形DP(),DP,算法,dp

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=6100;
int h[N],ne[N],e[N],idx;
int happy[N];
bool has_father[N];
int f[N][2];
bool st[N];
int root=1;
//建表
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u)
{
    f[u][1]=happy[u];//如果选当前节点u,就可以把f[u,1]先怼上他的高兴度
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        //状态转移部分
        f[u][0]+=max(f[j][1],f[j][0]);
        f[u][1]+=f[j][0];
    }
}
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>happy[i];
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b;cin>>a>>b;
        add(b,a);
        //若有父节点标记一下
        has_father[a]=true;
    }
    //找树根 树根没有父节点
    while(has_father[root]) root++;
    dfs(root);
    cout<<max(f[root][0],f[root][1]);//输出不选根节点与选根节点的最大值
    return 0;
}

树的最长路径

给定一棵树,树中包含 n 个结点(编号1~n)和 n−1 条无向边,每条边都有一个权值。

现在请你找到树中的一条最长路径。

换句话说,要找到一条路径,使得使得路径两端的点的距离最远。

注意:路径中可以只包含一个点。

输入格式

第一行包含整数 n。

接下来 n−1 行,每行包含三个整数 ai,bi,ci,表示点 ai 和 bi 之间存在一条权值为 ci 的边。

输出格式

输出一个整数,表示树的最长路径的长度。

数据范围

1≤n≤10000
1≤ai,bi≤n
−105≤ci≤105

输入样例:

6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

输出样例:

22

树形DP(),DP,算法,dp

 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e5+10;
int h[N],ne[N],w[N],e[N],idx;
int n;
int ans=0;
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
//father表示u的父节点,因为该图为无向图,并且迭代过程中不能回到父节点,所以要特殊标记.
int  dfs(int u,int father)
{
    //因为题目描述中有:注意:路径中可以只包含一个点
    //所以题目中的结果一定不为负数,负的路径由此可以忽略掉
    int d1=0,d2=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==father) continue;
        int d=dfs(j,u)+w[i];//求出路径的长度
        if(d>=d1) d2=d1,d1=d; //d1,d2求出以该点为顶点的最长路径
        else if(d>d2) d2=d;//最长路径和次长路径
    }
    ans=max(ans,d1+d2);
    return d1;
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b,c;cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1);
    cout<<ans<<endl;
    return 0;
}

D. Apple Tree

蒂莫菲的花园里长着一棵苹果树;它是n个顶点的有根树,根在顶点1中(顶点编号从1到n)。树是一个没有循环和多条边的连通图。这棵树很不寻常,它的根向上生长。然而,对于程序员的树来说,这是很正常的。苹果树很年轻,所以上面只会长两个苹果。苹果会生长在某些顶点(这些顶点可能是相同的)。苹果长出来后,蒂莫菲开始摇晃苹果树,直到苹果掉下来。每次Timofey摇动苹果树时,每个苹果都会发生以下情况:让苹果现在位于顶点u。如果一个顶点u有一个子顶点,苹果就会移动到它上面(如果有几个这样的顶点,苹果可以移动到其中的任何一个)。否则,苹果就会从树上掉下来。可以看出,在有限的时间后,两个苹果都会从树上掉下来。Timofey有苹果可以生长的顶点的q假设。他假设苹果可以在顶点xyy中生长,并想知道苹果可以从树上掉落的顶点对(a,b)的数量,其中a——从顶点x掉落的苹果将从顶点掉落,b——从顶点yy掉落的苹果。帮他做这个。 (多组输入 并且1时根节点)

输入样例 

2

5

1 2

3 4

5 3

3 2

4

3 4

5 1

4 4

1 3

3

1 2

1 3

3

1 1

2 3

3 1

 

输出样例 

2
2
1
4
4
1
2
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=5e5+10;
int h[N],ne[N],e[N],idx,w[N];
int cnt[N];
int n;
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
void dfs(int u,int father)
{
	if(w[u]==1&&u!=1)
	{
		cnt[u]=1;
		return ;
	}
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(father==j) continue;
		dfs(j,u);
		cnt[u]+=cnt[j];
	}
}
int main()
{
	int t;cin>>t;
	while(t--)
    {
    	cin>>n;
    	memset(h,-1,sizeof 4*(n+1));
    	memset(cnt,0,sizeof 4*(n+1));
    	memset(w,0,sizeof 4*(n+1));
    	for(int i=1;i<n;i++)
    	{
    		int a,b;cin>>a>>b;
    		add(a,b);
    		add(b,a);
    		w[a]++;
    		w[b]++;
		}
		dfs(1,-1);
		int q;
		cin>>q;
		while(q--)
		{
			int a,b;cin>>a>>b;
			cout<<(ll)cnt[a]*cnt[b]<<endl;
		}
	}
	return 0;
}

 文章来源地址https://www.toymoban.com/news/detail-705595.html

到了这里,关于树形DP()的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++---树形DP---树的最长路径(每日一道算法2023.5.4)

    注意事项: 本题为\\\"树与图的DFS深度优先遍历—树的重心\\\"的近似题,同时涉及到 单链表模拟邻接表存储图 的操作,建议先理解那篇文章。 题目: 给定一棵树,树中包含 n 个结点(编号1~n)和 n−1 条无向边,每条边都有一个权值。 现在请你找到树中的一条最长路径。 换句话

    2024年02月02日
    浏览(36)
  • 动态规划报告(树形DP+概率DP

    树形 DP,即在树上进行的 DP。由于树固有的递归性质,树形 DP 一般都是递归进行的。一般需要在遍历树的同时维护所需的信息 以一道题目为例 2022CCPC桂林站G Group Homework No, we don’t want group homework. It’s the place where 1+11 can be true. However, you are currently the leader of a group with three

    2024年02月12日
    浏览(46)
  • 动态规划-树形DP

    链接:https://www.acwing.com/problem/content/848/ 给定一颗树,树中包含 n n n 个结点(编号 1 ∼ n 1 sim n 1 ∼ n )和 n − 1 n-1 n − 1 条无向边。 请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。 重心定义:重心是指树中的一个结点,如果将这个点删除后,剩

    2024年02月08日
    浏览(38)
  • 动态规划之树形DP

    树形DP是指在“树”这种数据结构上进行的动态规划:给出一颗树,要求以最少的代价(或取得最大收益)完成给定的操作。通常这类问题规模比较大,枚举算法效率低,无法胜任,贪心算法不能求得最优解,因此需要用动态规划进行求解。 在树上做动态规划显得非常合适,

    2024年02月05日
    浏览(44)
  • 树形DP()

    Ural 大学有 N 名职员,编号为 1∼N。 他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。 每个职员有一个快乐指数,用整数 Hi 给出,其中 1≤i≤N。 现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。 在满足这个条件的前提下,主

    2024年02月09日
    浏览(30)
  • 动态规划——树形DP 学习笔记

    前置知识:树基础。 树形 DP,即在树上进行的 DP,最常见的状态表示为 (f_{u,cdots}) ,表示以 (u) 为根的子树的某个东东。 本文将讲解一些经典题目(树的子树个数、树的最大独立集、树的最小点覆盖、树的最小支配集、树的直径、树的重心、树的中心),以及一些常见形

    2024年02月08日
    浏览(37)
  • [ACM学习] 树形dp之换根

    总的来说: 题目描述:一棵树求哪一个节点为根时,XXX最大或最小 分为两步:1. 树形dp  2. 第二次dfs 如果暴力就是 O(n^2) , 当从1到2的时候,2及其子树所有的深度都减一,其它的点,所有的深度都加一。写成递推方程如下: 思路是:第一遍 dfs 遍历的时候先把以某一确定点

    2024年01月24日
    浏览(28)
  • 动态规划树形DP课后习题蓝桥舞会

      蓝桥舞会 题目描述 蓝桥公司一共有n名员工,编号分别为1~n。 他们之间的关系就像一棵以董事长为根的树,父节点就是子节点的直接上司。每个员工有一个快乐指数aj。 现蓝桥董事会决定举办一场蓝桥舞会来让员工们在工作之余享受美好时光,不过对于每个员工,他们都

    2024年02月21日
    浏览(43)
  • 【ICPC2022济南站】【树形dp】【删物品背包dp】C.DFS Order 2

    题目链接:https://codeforces.com/gym/104076/problem/C 简要题意:给定一棵n个点的有根树,对于所有的二元组 ( i , j ) (i,j) ( i , j ) 求这颗树所有可能的dfs序中有多少个dfs序满足第 i i i 个点出现在dfs序第 j j j 个位置。 赛场上假了无数次以后,我终于才理清楚了这题的dp思路。 状态定义

    2024年02月13日
    浏览(32)
  • 动态规划day09(打家劫舍,树形dp)

    目录 198.打家劫舍 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难 213.打家劫舍II 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难 337.打家劫舍 III(树形dp) 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中

    2024年01月23日
    浏览(91)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包