热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

CF161DDistanceinTree树形DP(套路,路径长度为k点对)

题意:n个节点的树,问有多少对(i,j)其最短距离等于K.n<5e4,k<5e2.(i,j),(j,i)视为一对.设d[i][j][01]从节点
题意:n个节点的树,问有多少对(i,j)其最短距离等于K.
n<=5e4,k<=5e2. (i,j),(j,i) 视为一对.


设d[i][j][0/1]从节点i向下或者向上走长度为J的方法数.

dp[i][j][0]+=dp[son][j-1][0].
dp[i][j][1]+=dp[fa][j-1][1]+dp[fa][j-1][0] (i-fa->fa的前i-1个子树中,总是往左走)

ans+=dp[i][k][1] 第i个点作为最深的点时,长度为k的路径数

#include 
using namespace std;
typedef long long ll;
const int N=5e4+5,M=5e2+5,inf=0x3f3f3f3f;
int n,k;
vector e[N];
int d[N][M][2];
void dfs(int u,int fa)
{
	d[u][0][0]=d[u][0][1]=1;
	if(fa)
	{
		d[u][1][1]++;
		for(int x=2;x<=k;x++)
			d[u][x][1]+=d[fa][x-1][1]+d[fa][x-1][0];
	}
	for(int i=0;i>n>>k;
	int u,v;
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans=ans+d[i][k][1];
	//	for(int x=1;x<=k;x++)
		//	printf("%d %d %d %d\n",i,x,d[i][x][0],d[i][x][1]);
	//	cout< 
 
 
 


法2:设d[u][x] 为子树u中,距离u长度为x的个数

当u作为路径的最高点时 

u作为终点:ans+=d[u][k]

起点和终点为u子树中的某两个点 并且路径经过u  : d[son[u]][x-1] * d[u][k-x]     另外一个点不能在u内 所以还要扣掉 dp[son[u]][x-1] * dp[u][k-x-1]

#include
#define ll long long
#define ld long double
#define pb push_back
#define x first
#define y second
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const int maxn=5e4+7,maxk=600;
ll dp[maxn][maxk];
vector adjlist[maxn];
int n,k,x,y;
ll ans;

void dfs(int cur,int par){
    dp[cur][0]++;
    for(auto u:adjlist[cur]){
        if(u!=par){
            dfs(u,cur);
            for(int i=0;i>n>>k;
    for(int i=1;i>x>>y;
        adjlist[x].pb(y);
        adjlist[y].pb(x);
    }
    dfs(1,0);
    ans/=2;
    cout< 
 




推荐阅读
  • 2018 HDU 多校联合第五场 G题:Glad You Game(线段树优化解法)
    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6356在《Glad You Game》中,Steve 面临一个复杂的区间操作问题。该题可以通过线段树进行高效优化。具体来说,线段树能够快速处理区间更新和查询操作,从而大大提高了算法的效率。本文详细介绍了线段树的构建和维护方法,并给出了具体的代码实现,帮助读者更好地理解和应用这一数据结构。 ... [详细]
  • 本文介绍如何使用线段树解决洛谷 P1531 我讨厌它问题,重点在于单点更新和区间查询最大值。 ... [详细]
  • poj 3352 Road Construction ... [详细]
  • 在C++程序中,文档A的每一行包含一个结构体数据,其中某些字段可能包含不同数量的数字。需要将这些结构体数据逐行读取并存储到向量中,随后不仅在控制台上显示,还要输出到新创建的文档B中。希望得到指导,感谢! ... [详细]
  • 在软件开发过程中,经常需要将多个项目或模块进行集成和调试,尤其是当项目依赖于第三方开源库(如Cordova、CocoaPods)时。本文介绍了如何在Xcode中高效地进行多项目联合调试,分享了一些实用的技巧和最佳实践,帮助开发者解决常见的调试难题,提高开发效率。 ... [详细]
  • 题目《BZOJ2654: Tree》的时间限制为30秒,内存限制为512MB。该问题通过结合二分查找和Kruskal算法,提供了一种高效的优化解决方案。具体而言,利用二分查找缩小解的范围,再通过Kruskal算法构建最小生成树,从而在复杂度上实现了显著的优化。此方法不仅提高了算法的效率,还确保了在大规模数据集上的稳定性能。 ... [详细]
  • Codeforces竞赛解析:Educational Round 84(Div. 2评级),题目A:奇数和问题
    Codeforces竞赛解析:Educational Round 84(Div. 2评级),题目A:奇数和问题 ... [详细]
  • 题目解析给定 n 个人和 n 种书籍,每个人都有一个包含自己喜好的书籍列表。目标是计算出满足以下条件的分配方案数量:1. 每个人都必须获得他们喜欢的书籍;2. 每本书只能分配给一个人。通过使用深度优先搜索算法,可以系统地探索所有可能的分配组合,确保每个分配方案都符合上述条件。该方法能够有效地处理这类组合优化问题,找到所有可行的解。 ... [详细]
  • 单片微机原理P3:80C51外部拓展系统
      外部拓展其实是个相对来说很好玩的章节,可以真正开始用单片机写程序了,比较重要的是外部存储器拓展,81C55拓展,矩阵键盘,动态显示,DAC和ADC。0.IO接口电路概念与存 ... [详细]
  • [转]doc,ppt,xls文件格式转PDF格式http:blog.csdn.netlee353086articledetails7920355确实好用。需要注意的是#import ... [详细]
  • 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4277。作者:Bob Lee,日期:2012年9月15日。题目描述:给定n个木棍,求可以组成的不同三角形的数量,最多15根木棍。 ... [详细]
  • 本报告对2018年湘潭大学程序设计竞赛在牛客网上的时间数据进行了详细分析。通过统计参赛者在各个时间段的活跃情况,揭示了比赛期间的编程频率和时间分布特点。此外,报告还探讨了选手在准备过程中面临的挑战,如保持编程手感、学习逆向工程和PWN技术,以及熟悉Linux环境等。这些发现为未来的竞赛组织和培训提供了 valuable 的参考。 ... [详细]
  • 在尝试对 QQmlPropertyMap 类进行测试驱动开发时,发现其派生类中无法正常调用槽函数或 Q_INVOKABLE 方法。这可能是由于 QQmlPropertyMap 的内部实现机制导致的,需要进一步研究以找到解决方案。 ... [详细]
  • 本文提出了一种基于栈结构的高效四则运算表达式求值方法。该方法能够处理包含加、减、乘、除运算符以及十进制整数和小括号的算术表达式。通过定义和实现栈的基本操作,如入栈、出栈和判空等,算法能够准确地解析并计算输入的表达式,最终输出其计算结果。此方法不仅提高了计算效率,还增强了对复杂表达式的处理能力。 ... [详细]
  • Android 构建基础流程详解
    Android 构建基础流程详解 ... [详细]
author-avatar
潘佳锐_340
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有