题解P4201: [NOI2008]设计路线
2024-10-08 16:58:39
发现给出了一棵树, 不是树的情况直接输出-1
考虑进行DP, 设f[i][0/1/2]为i的子树中选小于等于0/1/2条边修路的方案数, 不妨对于一个节点, 先考虑正好相等的情况, 假设当前扫到了一个节点v, 则有
\[f[i][0] = \max\{f[i][0]\, f[v][2]+1\} \\
f[i][1] = \min\{\max\{f[i][1], f[v][2]+1\}, \max\{f[i][0], f[v][1]\}\} \\
f[i][2] = \min\{\max\{f[i][2], f[v][2]+1\}, \max\{f[i][1], f[v][1]\}\}
\]
f[i][1] = \min\{\max\{f[i][1], f[v][2]+1\}, \max\{f[i][0], f[v][1]\}\} \\
f[i][2] = \min\{\max\{f[i][2], f[v][2]+1\}, \max\{f[i][1], f[v][1]\}\}
\]
接下来前缀min一下即可, 注意到要2->1->0更新, 并且要前缀min
接下来考虑DP出方案数, 发现我们所求的f[1][2]的最大值是\(O(log_3 n) \leq 11\)的, 因此设计状态时要把这个作为一个维度
咕咕咕
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _ 100005
#define rep for(int t=0; t<=f[1][2]; ++t)
int f[_][3], g[_][20][3], inf=0x3f3f3f3f;
int Next[_<<1], ver[_<<1], head[_], tot;
int n, m, q;
int gv(int x, int y, int z){
if(x>=0 && y>=0 && z>=0) return g[x][y][z]; return 0;
}
void dfs1(int u, int fa){
f[u][0] = 0, f[u][1] = inf, f[u][2] = inf;
for(int i=head[u]; i; i=Next[i]){
int v=ver[i]; if(v == fa) continue; dfs1(v, u);
f[u][2] = min(max(f[u][2], f[v][2]+1), max(f[u][1], f[v][1]));
f[u][1] = min(max(f[u][1], f[v][2]+1), max(f[u][0], f[v][1]));
f[u][0] = max(f[u][0], f[v][2]+1);
}
f[u][1] = min(f[u][0], f[u][1]); f[u][2] = min(f[u][2], f[u][1]);
}
void dfs2(int u, int fa){
rep g[u][t][0]=1, g[u][t][1]=g[u][t][2]=0;
for(int i=head[u]; i; i=Next[i]){
int v=ver[i]; if(v == fa) continue; dfs2(v, u);
rep {
g[u][t][2] = gv(u, t ,2)*gv(v, t-1, 2) + gv(u, t, 1)*gv(v, t, 1); g[u][t][2]%=q;
g[u][t][1] = gv(u, t, 1)*gv(v, t-1, 2) + gv(u, t, 0)*gv(v, t, 1); g[u][t][1]%=q;
g[u][t][0] = gv(u, t, 0)*gv(v, t-1, 2); g[u][t][0]%=q;
}
}
rep (g[u][t][1]+=g[u][t][0])%=q, (g[u][t][2]+=g[u][t][1])%=q;
}
void add(int u, int v){
ver[++tot]=v, Next[tot]=head[u], head[u]=tot;
}
signed main(){
scanf("%lld%lld%lld", &n, &m, &q);
if(m != n-1) return (puts("-1"), puts("-1"), 0);
for(int i=1; i<=m; ++i){
int x, y; scanf("%lld%lld", &x, &y); add(x, y); add(y, x);
}
dfs1(1, 0); dfs2(1, 0);
printf("%lld\n%lld\n", f[1][2], gv(1, f[1][2], 2));
}
最新文章
- Xamarin的不归路-生成安卓错误3
- ASP.NET MVC 之自定义HtmlHelper
- Unity上一页下一页切换功能实现源码(仅供参考)
- 02-C#入门(循环)
- Des加解密算法
- ytu 1998:C语言实验——删除指定字符(水题)
- CAM350测量
- ViewPage 一次滑动多页
- Result Maps collection does not contain value for...
- 我的第一篇blog—— 一起来赛马呀
- TCP协议的性能评测工具 — Tcpdive开源啦
- 广州.NET微软技术俱乐部微信群有用信息集锦(10) - 大量json数据压缩方案
- 【DWM1000】 code 解密8一 TAG接收blink response 信号
- mysql密码的坑
- @staticmethod和classmethod
- java学习笔记(二):枚举值
- redis的安装使用以及在python中操作redis
- redis make jemalloc
- QT构建窗体(父窗体传为野指针)异常案例
- oracle数据库归档与非归档
热门文章
- springboot的maven多模块项目架构微服务搭建——依赖方式的多模块演化为微服务项目
- PHP中strlen和mb_strlen函数的使用方式的不同
- 009.Oracle数据库 , between关键字判断日期在两者之间
- spark aggregate算子
- DataFoundation比赛总结
- 【pwnable.kr】 unlink
- 3-Java逻辑控制语句
- Golang go-gin 注册路由
- C++ 把数组的元素乘以2在输出
- 黑马oracle_day01:02.oracle的基本操作