首页 > 其他分享 >【CF1146F】Leaf Partition

【CF1146F】Leaf Partition

时间:2023-07-02 15:00:12浏览次数:42  
标签:Leaf int Partition times fa 拼接 CF1146F dp mod

这个题还是蛮有趣的,其实弄清楚这个染色的方案,这个题还是简单的。

本质上只是对于考虑对于连通块染色,但是带有一些限制。

所以我们考虑在 LCA 上拼接若干条根到叶子的路径。

那我们就可以依据这一想法来设计状态。

第一是这个点没有染色,那我们记这一状态为 \(h\)。

第二是这个点连接着一条到一个叶子的链,值得注意,这种情况不符合最小联通图的定义,所以不可以作为一个根来算答案,要一直连到祖先上,记为 \(f\)。

第三是拼接了至少两条同色的到叶子的链,记为 \(g\)。

考虑依次插入 \(v\) 这个子节点的答案,那么转移就很明显了:

首先是如果不染,那么这个点可以随便算,但是注意不能算 \(f\) 这种不合法的答案。

\[h_u = \prod(h_v + g_v) \]

如果只染一条链,那么可以从无色染到有,也可以原本有色,不进行拼接。

\[f_u = f_u \times (g_v + h_v) + h_u \times (g_v + f_v) \]

如果是染了至少两条链,那就可由一个一条或者多条的连上来,或者随便算一下儿子。

\[g_u = g_u \times (f_v + 2 \times g_v + h_v) + f_u \times (g_v + f_v) \]

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define lc u << 1
#define rc u << 1 | 1
#define int long long
// g -> f -> h 
using namespace std;

const int N = 2e5 + 5, mod = 998244353;

vector <int> e[N];
int n, g[N], h[N], f[N];

void dp (int u) {
	if (! e[u].size()) { g[u] = 1; return ; }
	h[u] = 1;
	for (int v : e[u]) {
		dp(v);
		g[u] = g[u] * (f[v] + 2 * g[v] + h[v]) + f[u] * (g[v] + f[v]);
		f[u] = f[u] * (g[v] + h[v]) + h[u] * (g[v] + f[v]);
		h[u] = h[u] * (h[v] + g[v]);
		g[u] %= mod, f[u] %= mod, h[u] %= mod;
	}
}
signed main () {
	ios :: sync_with_stdio(0);
	cin >> n;
	for (int i = 2, fa; i <= n; i ++)
		cin >> fa, e[fa].push_back(i);
	dp(1), cout << (g[1] + h[1]) % mod;
	return 0;
}

标签:Leaf,int,Partition,times,fa,拼接,CF1146F,dp,mod
From: https://www.cnblogs.com/Custlo/p/17520809.html

相关文章

  • 003-Leaflet-各地图切换
    一、代码<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=edge"><metaname="viewport"content="......
  • ESP(EFI System Partition)分区是UEFI固件中的一个特殊分区,通常位于硬盘上的第一个分区,
    ESP(EFISystemPartition)分区是UEFI固件中的一个特殊分区,通常位于硬盘上的第一个分区,用于存储引导加载程序、UEFI应用程序和其他与系统启动相关的文件。ESP分区使用FAT32文件系统,并拥有特定的分区类型GUID(GUIDPartitionTable,GPT)。ESP分区的主要作用是提供一个可被UEFI固件直接......
  • Codeforces 1603D. Artistic Partition
    题目链接:D-ArtisticPartition题目大意:要求将\([1,n]\)分成\(k\)段,使得每段对应的\(c(l,r)\)之和最小,其中\(c(l,r)=\sum_{i=l}^r\sum_{j=i}^r[\gcd(i,j)\gel]\)。首先注意到当\(r<2l\)时,\(c(l,r)=r-l+1\)。所以当\(2^k-1\gen\)时答案即为\(n\)。考虑\(\texttt......
  • ORA-14099: all rows in table do not qualify for specified partition
    1.创建分区表createtablerange_part_range(idnumber,deal_datedate,contentsvarchar2(1000))partitionbyrange(deal_date)(partitionp1valueslessthan(to_date('2015-01-21','yyyy-mm-dd')),partitionp2valueslessthan(to_date......
  • Thymeleaf对象
    1. Thymeleaf 基本对象   115-117模板引擎提供了一组内置的对象,这些内置的对象可以直接在模板中使用,这些对象由#号开始引用,我们比较常用的内置对象1.2 #request 表示 HttpServletRequest1.3  #session 表示 HttpSession 对象1.4 session 对象,表示 HttpSession 对......
  • 基于SpringBoot+MyBatis+Thymeleaf的学生管理系统搭建
    学生管理系统Maven工程搭建【步骤】:打开IDEA工具,选择创建一个新工程。选择SpringInitializr,点击Next按钮。大家也可以通过Spring提供的在线创建的方式创建工程,访问(https://start.spring.io),然后将创建后的工程代码zip包解压后,使用IDEA导入工程。这种方式不在本文描述......
  • thymeleaf for循环第一次后中断循环
     thymeleaffor循环第一次后中断循环<divth:each="processList,iterStat:${dict.processList}"><th:blockth:if="${iterStat.index==0}"><spanstyle="width:80%;display:block;"class="p......
  • Oracle partition by 用法及函数
    Oraclepartitionby--函数row_number、rank、dense_rank--row_number:序号,不重复;例如:1,2,3,4,5--rank:排序,重复;例如:1,2,2,2,5--dense_rank:排序,不重复;例如:1,2,2,2,3--sum:求和,本行排名之前(包括本行排名)的总和--count:技术,包括本行排名一共有多少名SELECTt.*FROM(S......
  • leetcode 561. Array Partition I
    Givenanarrayof2nintegers,yourtaskistogrouptheseintegersintonpairsofinteger,say(a1,b1),(a2,b2),...,(an,bn)whichmakessumofmin(ai,bi)forallifrom1tonaslargeaspossible.Example1:Input:[1,4,3,2]Output:4Explanation:......
  • springboot集成themeleaf报Namespace 'th' is not bound问题的解决
    问题描述在我们想要在html前端页面使用th:符号时,发现他一直报错问题解决在html标签的最上方,也就是这里:加上这样一句代码:(加在html标签里面!!!)xmlns="http://www.w3.org/1999/xhtml"xmlns:th="http://www.thymeleaf.org"这样就能够解决这个问题啦!......