首页 > 其他分享 >QOJ2376 Game on a Tree (树形 dp)

QOJ2376 Game on a Tree (树形 dp)

时间:2024-07-02 13:42:37浏览次数:16  
标签:std 匹配 int Tree long Game QOJ2376 dp define

QOJ2376 Game on a Tree

树形 dp

因为题目限制对于两个人等价,所以朴素的,考虑将 \(u\) 与祖先和后代连边,构成一个新的无向图。那么题目就变成:在无向图中选一点,每一次操作就是走一步到新的点,谁先不能走,那么另一个人获胜。

先说结论:当无向图有完美匹配时,后手胜,反之先手胜

证明:若有完美匹配,说明所有点都在匹配中,先手选点后,后手选与之匹配的点,那么一定能选完所有点并且后手选到最后一个,后手胜;反之,说明存在一个点不在最大匹配中,先手选该点,那么后手选择相邻的点一定在匹配中(否则这两点又构成匹配),先手下一次选的点同样在匹配中(否则构成增广路,与最大匹配矛盾),那么就回到上面的情形但角色互换,先手胜。

回到原题,我们无法建出无向图,考虑树形 dp。设 \(f_u\) 表示 \(u\) 子树中最少有多少点没有匹配,设 \(g_u=\sum\limits_{v\in son_u}f_v\),根据 \(u\) 点和子树中任意一点能够形成匹配,转移为:

\[f_u=\begin{cases} g_u-1, & \text{if }g>0 \\ 1, & \text{otherwise} \end{cases} \]

答案判断 \(f_1\) 即可。

复杂度 \(O(n)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
int n;
int f[N];
std::vector<int> e[N];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::cin >> n;
	
	for(int i = 1; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		e[u].pb(v);
		e[v].pb(u);
	}
	
	auto dfs = [&](int u, int fa, auto &self) -> void {
		int g = 0;
		for(auto v : e[u]) {
			if(v == fa) continue;
			self(v, u, self);
			g += f[v];
		}
		if(g) f[u] = g - 1;
		else f[u] = 1;
	};
	dfs(1, 0, dfs);

	std::cout << (f[1] ? "Alice\n" : "Bob\n");

	return 0;
}

标签:std,匹配,int,Tree,long,Game,QOJ2376,dp,define
From: https://www.cnblogs.com/FireRaku/p/18279721

相关文章

  • CF950Div3 G. Yasya and the Mysterious Tree(01Trie)
    Problem题目地址Solution设\(s[u]\)是根到\(u\)路径上的异或和,树上任意两点\(u,v\)的路径异或和可表示为\(s[u]\opluss[v]\)。考虑查询操作?vx即求\(\max\{s[v]\opluss[u]\oplusx|\\1\leu\len,u\not=v\}\),若把\(s[v]\oplusx\)看作一个整体......
  • Vue Ant Design中a-tree组件支持点击父节点名称(title\label)所有子节点选中
    核心代码<a-treeref="treeRef"class="draggable-tree"v-if="treeData.length":tree-data="treeData"......
  • sourcetree使用ssh拉取代码报错?看下是不是ssh客户端的问题以及相应的解决方案看这里~~
    相信很多软件开发的同学都很熟悉sourcetree,如果也有同学在使用过程中出现ssh拉取代码出现如下报错的问题这里比较头疼的是没法交互输入y确认缓存秘钥。Theserver'shostkeyisnotcachedintheregistry.Youhavenoguaranteethattheserveristhecomputeryouthi......
  • Leetcode 3203. Find Minimum Diameter After Merging Two Trees
    Leetcode3203.FindMinimumDiameterAfterMergingTwoTrees1.解题思路2.代码实现题目链接:3203.FindMinimumDiameterAfterMergingTwoTrees1.解题思路这一题的话算是一个拓扑树的题目?总之就是从树的叶子节点不断向上遍历,不断地删除已访问的叶子节点,并加入......
  • [题解]CF1714F Build a Tree and That Is It
    思路由于题目中说这是一棵无根树,不太方便思考,于是,我们可以假装把这棵树看做有根树。首先我们令\(d_1,d_2,d_3\)分别表示从根节点到节点\(1,2,3\)的长度(不算相交部分)。那么我们可以得到下式:\[\left\{\begin{matrix}d_{12}=d_1+d_2\\d_{13}=d_1+d_3\\......
  • [题解]CF1741D Masha and a Beautiful Tree
    思路我们可以观察样例,不难发现:对于任意一段长度为\(2^k\)的区间中,如果最大值减最小值加\(1\)等于此区间的长度,那么一定有解。因为,我们的目标是使整个序列升序排列。因此,我们在一个区间内的最大值减最小值加\(1\)与区间长度是相等的。所以,我们可以用上述结论为判断无解的......
  • WPF TreeView 三层绑定模板
    在WPF应用程序中,使用TreeView来展示三层数据结构是一个常见的需求。为此,你需要定义适当的数据绑定和模板。以下是一个完整的示例代码,展示如何实现这一点。数据模型首先,我们需要定义三层数据模型。假设我们有三层数据结构:RootItem包含ChildItem,ChildItem又包含SubChildItem。pub......
  • CF1770E Koxia and Tree
    题目描述给定一棵\(n\)个点的树,在\(k\)个位置上存在蝴蝶,我们需要给\(n-1\)条边定向,如果一条边的起点有蝴蝶且终点没有蝴蝶,那么蝴蝶将被移动到终点,我们会按照给定边的顺序移动,问最终所有蝴蝶的树上距离的和的期望,答案除于\(\frac{k(k-1)}{2}\),对\(998244353\)取模\[k\len\le300......
  • [题解]AT_arc116_d [ARC116D] I Wanna Win The Game
    思路因为题目与二进制有关,考虑往二进制的方向思考。定义\(dp_{i,j}\)表示在所有的\(n\)个数中,当前在决策对于每一个数在二进制表示下的第\(i\)位是\(0\)还是\(1\),且和为\(j\)的方案数。因为异或需要满足对于所有\(a_i\)表示为二进制后每一位\(1\)的个数均为偶数......
  • ABC359 G - Sum of Tree Distance
    题目链接题目大意给出一棵树,树上每个节点都有一种颜色,求所有颜色相同的节点两两之间距离的总和。 题解想来写题解主要是看了一下官方解法都写的需要“重心分解”,应该是对应中文语境下的树的点分治。实际上点分治写起来很费事,可以用启发式合并替代。具体来说,dfs时每个节点......