当前位置: 首页 > news >正文

AGC073C 赛后补题记录

感觉还是因为考场上没有用草稿纸,一直在原地思考。在草稿纸上多画画,可以拓展可能的入手点,更直观地刻画。

考虑将整棵树划分为若干个块,其中同一个块内每个点的选择方案都相同,对应的 \(x\) 也相同,并且每个块是极大的。

每个块可能会选择包掉其他的块,手模一下发现如果包的时候不把对应的整个块包掉是不优的。

进一步的,如果包掉了一个块,同时会把这个块包的块也包掉。

也就是说,这具有传递性,这种关系形成了一个森林。对于一个块,其会包掉 \(x\) 比它大的块,不会包 \(x\) 比它小的块。

按照 \(x\) 从大到小加入所有块,加入一个块的时候会包掉其相邻的以加入的块的包。

所以,如果能确定每个块的 \(x\),就能唯一确定所有的包的方案。

这也同时证明了,块的划分是极大的。因为如果一个 \(x\) 较大的块和一个 \(x\) 较小的块合并,由于 \(x\) 较小的块包掉了 \(x\) 较大的块,从其包中去掉 \(x\) 较大的块后 \(x\) 变为 负数,这样 \(x\) 较大的块就不优了。

再看每一个块,因为已经确定了这个块的包,将块外的贡献挂在块内对应的连接的点上。

该块内部形成了一棵树,考虑块内每个点 \(u\) 的子树权值总和 \(s_u\),令 \(r\) 为该块的根,\(S\) 为块内点集,那么应满足 \(\forall u\in S, \ 0\le s_u\le s_r\)

注意 \(s_u\) 是由 \(\sum_{v\in son(u)} s_v\),以及挂在 \(u\) 上的权值贡献,以及 \(u\) 本身的权值三部分构成。由于 \(u\) 的权值可以取 \([-n + 1, 1]\),发现 \(s_u \in [0, 1]\) 都是可以取到的,所以可以看成每个 \(s_u\) 都是一个随机变量,可以取到 \([0, 1]\) 的所有值。

实际求答案时其实不需要考虑块之间的 \(x\) 的大小顺序,需要考虑的条件只有 \(0\le s_u\le s_r\)。上面只是有助于我们分析。

综上所述,我们需要对于每一种块的划分方案,求所有块的贡献乘积的总和。

现在考虑求一个块的贡献:对于一个大小为 \(k\) 的块,枚举 \(s_r = x\),那么贡献为 \(\displaystyle \int_{x = 0} ^ 1 x ^ k \left (\displaystyle \int_{y = 0} ^ x 1 \ dy \right ) ^ {k - 1} dx = \displaystyle \int_{x = 0} ^ 1 x ^ {2k - 1} dx = \dfrac 1 {2k}\)

树上背包统计答案,时间复杂度为 \(\mathcal O(n ^ 2)\)


点击查看代码
#include <bits/stdc++.h>
#define ll int
#define LL long long
#define uLL unsigned LL
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb emplace_back
#define i128 __int128
const ll maxn = 5010, mod = 998244353, M = 1e5, inf = 1e9;
template <class T>
void rd(T &x) {char ch; ll f = 0;while(!isdigit(ch = getchar()))if(ch == '-') f = 1;x = ch - '0';while(isdigit(ch = getchar()))x = (x << 1) + (x << 3) + ch - '0';if(f) x = -x;
}
ll power(ll a, ll b = mod - 2, ll p = mod) {ll s = 1;while(b) {if(b & 1) s = 1ll * s * a % p;a = 1ll * a * a % p, b >>= 1;} return s;
}
template <class T1, class T2>
void add(T1 &x, const T2 y) { x = x + y >= mod? x + y - mod : x + y; }
template <class T1, class T2>
void sub(T1 &x, const T2 y) { x = x < y? x + mod - y : x - y; }
template <class T1, class T2>
ll pls(const T1 x, const T2 y) { return x + y >= mod? x + y - mod : x + y; }
template <class T1, class T2>
ll mus(const T1 x, const T2 y) { return x < y? x + mod - y : x - y; }
template <class T1, class T2>
void chkmax(T1 &x, const T2 y) { x = x < y? y : x; }
template <class T1, class T2>
void chkmin(T1 &x, const T2 y) { x = x < y? x : y; }
using namespace std;ll n, f[maxn][maxn], siz[maxn], inv[maxn];
vector <ll> to[maxn];void dfs(ll u, ll fa = 0) {siz[u] = 1, f[u][1] = 1;for(ll v: to[u]) {if(v == fa) continue;dfs(v, u);for(ll i = siz[u]; i; i--) {ll val = f[u][i]; f[u][i] = 0;for(ll j = 0; j <= siz[v]; j++)add(f[u][i + j], 1ll * val * f[v][j] %mod);}siz[u] += siz[v];}for(ll i = 1; i <= siz[u]; i++)add(f[u][0], 1ll * f[u][i] * inv[i] %mod);
}int main() {rd(n); inv[1] = 1;for(ll i = 2; i <= n; i++)inv[i] = (mod - mod / i) * 1ll * inv[mod % i] %mod;for(ll i = 1; i <= n; i++) inv[i] = 1ll * inv[i] * (mod / 2 + 1) %mod;for(ll i = 1; i < n; i++) {ll u, v; rd(u), rd(v);to[u].pb(v), to[v].pb(u);}dfs(1);printf("%lld\n", 1ll * f[1][0] * power(n, mod - 1 - n) %mod);return 0;
}
http://www.hskmm.com/?act=detail&tid=20884

相关文章:

  • LuatOS赋能Air780EPM:FTP通信开发教程正式上线!
  • DM40万用表为何全网爆火?!它有哪些与众不同?DM40万用表比肩千元级表,让您轻松实现专业级测量自由!
  • 树形dp [POI 2013] LUK-Triumphal arch
  • 【论术】t-design tree组件判断点击了角标还是label
  • leetCode刷题记录1
  • k8s下部署kuboard
  • ACL 第一周模拟赛题解
  • 万象EXCEL开发(三)格式解读calcChain.xml——东方仙盟练气期 - 指南
  • 302、寄门人
  • 达梦数据库用户开启限制白名单导致自身无法登录
  • 【转发】Nginx配置https
  • 本地文件多人多端同步工具:10款高性价比选择
  • 打破AI孤岛:CIO集成实战指南
  • 密码学学习记录(四)
  • Sharding-Proxy、ShardingSphere 和 Sharding-JDBC区别
  • echarts4升级为echarts5的常见问题
  • ISO 周计算 记录
  • 从 “被动耗能” 到 “主动优化”:MyEMS 开启商业建筑能源管理 “新范式”
  • 【故障排查】视频汇聚EasyCVR接入设备通道数为0?通道编码长度不规范导致
  • 来信小程序管理系统:匿名信息传递与社交互动平台
  • PCIe加速卡设计资料:416-基于Kintex Ultrasacle的万兆网络光纤 PCIe加速卡
  • 多生产者,多消费者
  • GEO优化实战指南:一周内让豆包、Deepseek、Kimi等推荐了我的插件
  • 房产楼盘小程序管理系统:助力房产营销数字化升级的优质解决方案
  • 高速信号处理设计方案:413-基于双XCVU9P+C6678的100G光纤加速卡
  • Teamcenter:结构管理器查询(又称:BOM结构查询)
  • 2025年最好用的同步云盘是哪个?一个老用户的真实体验分享
  • 使用 ShedLock 实现多实例定时任务单执行的常见错误及解决办法
  • 1_二分查找
  • AI元人文:悟空博弈专用芯片