题意 题目链接 树上的棋子博弈,每个点有权值。你可以添加一条边以试图反败为胜,不同的加边方法根据权值有一个代价,需要最小化这个代价。 解析 我们首先定义一个结点先手必败是 lose,先手必胜是 win,容易发现,叶子结点一定是 lose,然后对于每一个非叶子结点,只要它有一个儿子是 lose,它就是 win,否则,该结点也是 lose。一遍 d…
标签: 博弈论
1 篇文章
标签
AC 自动机 1ACM 16AC自动机 1Border 树 1CCPC 1CF 1CSP 1dfs序 1dp 10dsu on tree 1fhq_treap 1gcd 1ICPC 9kmp 2LCP 1Manacher 1MCMF 1multiset 1NOIp 0OI 5PAM 1Segmen_Tree 0set 1SOSDP 1tarjan 1Trie 1Trie 树 1二分 1二分图 1交互 1交互题 1位运算 1倍增 2值域分块 1决策单调性 1凸包 1凸轮 0分块 2分治 2前缀和 3割点 1动态规划 9博客 1博弈论 1双指针 2可并堆 1同余 0后缀数组 1后缀自动机 1吸纳段数 0图匹配 1图论 11块状链表 1堆 2字符串 4字符串匹配 1字符串哈希 1小白月赛 1左偏树 1差分 2平衡树 2应用文 1强连通分量 1归并排序 1思维 15扩展欧拉定理 1拓扑 1排列组合 0数学 5数据结构 2数论 4整体二分 1整除 0文艺 0文艺味 0暖心 0暴力 1最大公因数 1最大流 1最小割 1最小生成树 1最小费用最大流 1构造 5树 8树形 dp 1树形dp 1树状数组 1树链剖分 3根号复杂度 1桥 0模拟 3模板 1母亲 1母亲节 1游戏 0游记 0点双 0牛客 2珂朵莉树 1生成树 1生物 1相同数 1社会 1离散化 1积性函数 0笛卡尔树 1筛法 0算法 4算法竞赛 2线性筛 1线段树 3组合 0组合数学 1结论题 3续写 1缩点 1网络流 4背包 1英语 1英语作文 1莫比乌斯反演 0计数 1计算几何 1诗歌 1贪心 4边双 0连通性 1链表 1预处理 1