【树形DP+换根思想】2022牛客多校加赛 H

news/2024/11/19 22:53:08/

登录—专业IT笔试面试备考平台_牛客网

题意:

思路:

这个虽然是树形DP,却用了换根的思想....

首先,后缀0的个数可以转化成min(cnt2,cnt5),其中cnt2为2的因子个数,cnt5为5的因子个数

然后进行DP

设dp[u][0/1]为,在除了u这棵子树中,2/5的因子个数

为什么要这么设计,我们发现,如果计算的结点是在子树里面的,那么lca就是u,子树的贡献直接就是sz[u]*cnt[u][0/1]

但是在这棵子树之外的贡献不能这么求,因此需要额外设计

然后转移就很简单:

dp[v][j]=dp[u][j]+(sz[u]-sz[v])*cnt[u][j]

最后统计贡献的时候加上子树部分的贡献,取min(cnt2,cnt5)就好了

Code:

#include <bits/stdc++.h>#define int long longusing namespace std;const int mxn=2e5+10;
const int mxe=1e6+10;
const int mxv=1e6+10;
const int mod=998244353;
const int Inf=1e18;vector<int> G[mxn];int N,Q;
int u,v,x;
int sz[mxn];
int dp[mxn][2],cnt[mxn][2];void init(){for(int i=1;i<=N;i++){if(i%2==0){int t=i,s=0;while(t%2==0) t/=2,s++;cnt[i][0]=s;}if(i%5==0){int t=i,s=0;while(t%5==0) t/=5,s++;cnt[i][1]=s;}}
}
void dfs1(int u,int fa){sz[u]=1;for(auto v:G[u]){if(v==fa) continue;dfs1(v,u);sz[u]+=sz[v];}
}
void dfs2(int u,int fa){for(auto v:G[u]){if(v==fa) continue;for(int j=0;j<=1;j++){dp[v][j]=dp[u][j]+(sz[u]-sz[v])*cnt[u][j];}dfs2(v,u);}
}
void solve(){cin>>N>>Q;init();for(int i=1;i<=N-1;i++){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}dfs1(1,0);dfs2(1,0);while(Q--){cin>>x;int res=1e18;for(int j=0;j<=1;j++){res=min(res,dp[x][j]+sz[x]*cnt[x][j]);}cout<<res<<'\n';}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}


http://www.ppmy.cn/news/999976.html

相关文章

宋浩概率论笔记(二)随机变量

本章节内容较多&#xff0c;是概率论与数理统计中最为重要的章节&#xff0c;对于概率密度和分布函数的理解与计算要牢牢掌握&#xff0c;才能在后期的学习中更得心应手。

怎么才能提升自己工作能力?

表现最好的员工通常是获得加薪和工作晋升的人。您可以采取某些措施来提高您的工作绩效&#xff0c;并帮助您的主管将您视为他们最好的员工之一。在本文中&#xff0c;我们列出了 12 个技巧&#xff0c;可以立即提高您的工作绩效。 什么是工作绩效&#xff1f; 工作绩效是指您…

雷达信号处理技术汇总

系列文章目录 《雷达简单介绍》 《信号类型&#xff08;雷达&#xff09;——雷达波形认识&#xff08;一&#xff09;》 《信号类型&#xff08;雷达&#xff09;——连续波雷达&#xff08;二&#xff09;》 《信号类型&#xff08;雷达&#xff09;——脉冲雷达&#xf…

分享:交流负载箱 0~9.999A 可调 步进1mA

前言 最近去客户那边&#xff0c;发现一个问题&#xff0c;他们的交流供电单元 测试很不方便。 需求 供电单元输出&#xff1a; AC220V 50HZ&#xff1b;漏电保护保护功能过载报警功能&#xff1b;超载保护功能&#xff1b; 总而言之&#xff0c;他们需要一台 交流的电子负…

Flask简介与基础入门

一、了解框架 Flask作为Web框架&#xff0c;它的作用主要是为了开发Web应用程序。那么我们首先来了解下Web应用程序。Web应用程序 (World Wide Web)诞生最初的目的&#xff0c;是为了利用互联网交流工作文档。 1、一切从客户端发起请求开始。 所有Flask程序都必须创建一个程序…

Python之pyinstaller打包exe填坑总结

一、起因 编写了一个提取图片中文字的python脚本&#xff0c;想传给同事使用&#xff0c;但是同事电脑上没有任何python环境&#xff0c;更没有安装python库&#xff0c;因此想到通过pyinstaller打包成exe程序传给同事使用&#xff0c;于是开始了不断地挖坑填坑之旅 import p…

【Uniapp 的APP热更新】

Uniapp 的APP热更新功能依赖于其打包工具 HBuilder&#xff0c;具体步骤如下&#xff1a; 1. 在 HBuilder 中构建并打包出应用程序 具体步骤&#xff1a; 1.点击发行&#xff0c;点击制作wgt包 2.根据需求修改文件储存路径和其他配置&#xff0c;点击确定 3.等待打包完成&a…

解决el-table打印时数据重复显示

1.表格数据比较多加了横向滚动和竖向滚动&#xff0c;导致打印出问题 主要原因是fixed导致&#xff0c;但是又必须得滚动和打印 方法如下&#xff1a; 1. 2. is_fixed: true,//data中定义初始值 3.打印时设置为false,记得要改回true if (key 2) { this.is_fixed false //打…