Luogu 3698 [CQOI2017]小Q的棋盘
2024-10-21 03:58:24
BZOJ 4813
虽然数据范围很迷人,但是想树形$dp$没有前途。
先发现一个事情,就是我们可以先选择一条链,最后要走到这一条链上不回来,走到链上的点每一个只需要一步,而如果要走这条链之外的点,一个点需要走两步。
这条链怎么选取?为了尽量减少步数,肯定是最长链。
现在有了一个显然的事情,如果限制步数$stp$不比最长链长度$mx$大的话,那么直接在最长链上走一走就好了,答案为$stp + 1$。
一棵树最少需要$mx + 2 * (n - mx - 1) = 2n - mx - 2$步走完,如果$stp$不小于这个值,那么一定能走完,答案为$n$。
剩下的情况只要先考虑走完最长链然后尽量分配步数到别的点上去就好了,答案为$mx + 1 + \left \lfloor \frac{stp - mx}{2} \right \rfloor$。
时间复杂度$O(n)$。
应该也有$dp$的办法吧。
Code:
#include <cstdio>
#include <cstring>
using namespace std; const int N = ; int n, stp, tot = , head[N], dep[N]; struct Edge {
int to, nxt;
} e[N << ]; inline void add(int from, int to) {
e[++tot].to = to;
e[tot].nxt = head[from];
head[from] = tot;
} inline void read(int &X) {
X = ; char ch = ; int op = ;
for(; ch > '' || ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} inline void chkMax(int &x, int y) {
if(y > x) x = y;
} void dfs(int x, int fat, int depth) {
dep[x] = depth;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if(y == fat) continue;
dfs(y, x, depth + );
}
} int main() {
read(n), read(stp);
for(int x, y, i = ; i < n; i++) {
read(x), read(y);
++x, ++y;
add(x, y), add(y, x);
} dfs(, , );
int mx = ;
for(int i = ; i <= n; i++)
chkMax(mx, dep[i] - ); if(stp <= mx)
return printf("%d\n", stp + ), ;
if(stp >= * n - mx - )
return printf("%d\n", n), ; printf("%d\n", mx + + (stp - mx) / );
return ;
}
最新文章
- jquery插件学习之元素顶部悬浮
- ipython安装
- ###Git使用问题
- c语言字符串库函数#include<;string.h>;
- 屏幕录制:SCR Screen Recorder Pro v0.14.3汉化破解版
- 仿桌面通知pnotify插件
- Lambda表达式的面纱(一)
- C# 坦克大战学习总结
- Arduino 各种模块篇 GPRS module 手机模块 短信 电话 上网 for texting, calling, internet
- log4j配置示例
- 关于HTML应用中的实操细节
- 计算机协议、标准以及OSI模型的简单介绍
- 412 6个题 BOM and DOM 定义计数器 网页跳转 网页前进后退
- 初入爬虫(java)
- c++11 function_typetraits备忘
- 【经验总结】 fisheye 3.1.5 安装、破解全过程 图文教程(2.0以上版本均可成功!)
- CCF 201709-2公共钥匙盒
- VGG——Very deep convolutional networks for large-scale image recognition
- iOS用户体验之-导航之道
- CSS3动画库——animate.css