首页 > 其他分享 >P9352 [JOI 2023 Final] Cat Exercise

P9352 [JOI 2023 Final] Cat Exercise

时间:2024-04-11 21:24:09浏览次数:22  
标签:子树 anc int pos Cat P9352 dep fa 2023

P9352 [JOI 2023 Final] Cat Exercise

树形 dp+trick+并查集

若我们以当前猫在的位置 \(u\) 为根,那么猫的下一步移动就会走到其中一个子树中。猫只有在我们把障碍放到当前的位置时才会移动,所以一定无法回到 \(u\) 点。要指定进入某个子树,只需要把其他子树都堵住即可。

考虑树形 dp。设 \(f_u\) 表示以 \(u\) 为根(猫所在位置)的最大移动次数。由于猫的终点无法确定,而起点一定在最高点,所以我们考虑从终点转移到起点。那么就考虑猫咪下一步会在哪些位置。设 \(pos_u\) 表示 \(u\) 子树中的最高点,那么有:

\(f_u=\max(f_u,f_{pos_v}+dist(u,pos_v))(a_u>a_{pos_v})\)

这样做最后答案就是最高点的 \(f_u\)。

我们直接钦定一个根是无法满足无后效性的,\(u\) 的转移是对于所有子树(包括其父亲所构成的子树)。考虑怎样满足无后效性。我们发现转移的时候一定有 \(a_u>a_{pos_v}\),所以我们按照 \(a\) 从小到大转移就可以。

每个点权都不同,所以考虑一个 trick,连边 \((a_u,a_v)\),这样子构成的新树与原树结构上相同,本质上只是编号变为点权,\(dist\) 数据结构维护。考虑如何找到 \(pos_v\),可以用并查集维护当前枚举过的点构成的连通块,枚举小根合并在大根上即可。

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

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

typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 200010;
int n;
i64 dep[N], anc[N][20], dp[N], fa[N], a[N];
std::vector<int> e[N];
void dfs(int u, int fa) {
	dep[u] = dep[fa] + 1;
	anc[u][0] = fa;
	for(int i = 1; i <= 19; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1];
	for(auto v : e[u]) {
		if(v == fa) continue;
		dfs(v, u);
	}
}
int lca(int u, int v) {
	if(dep[u] < dep[v]) std::swap(u, v);
	for(int i = 19; i >= 0; i--) if(dep[anc[u][i]] >= dep[v]) u = anc[u][i];
	if(u == v) return u;
	for(int i = 19; i >= 0; i--) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
	return anc[u][0];
}
int dist(int u, int v) {
	int rt = lca(u, v);
	return dep[u] + dep[v] - 2 * dep[rt];
}
int find(int x) {
	if(x != fa[x]) fa[x] = find(fa[x]);
	return fa[x];
}
void Solve() {
	std::cin >> n;
	for(int i = 1; i <= n; i++) {
		fa[i] = i;
		std::cin >> a[i];
	} 
	for(int i = 1; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		e[a[u]].pb(a[v]), e[a[v]].pb(a[u]);
	}
	dfs(1, 0);
	for(int u = 1; u <= n; u++) {
		for(auto v : e[u]) {
			int fv = find(v);
			if(fv < u) fa[fv] = u, dp[u] = std::max(dp[u], dp[fv] + dist(u, fv));
		}
	}
	std::cout << dp[n] << "\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	Solve();

	return 0;
}

标签:子树,anc,int,pos,Cat,P9352,dep,fa,2023
From: https://www.cnblogs.com/FireRaku/p/18130044

相关文章

  • Educational Codeforces Round 154 (Rated for Div. 2)
    B和C写的太慢了。吃了不该吃的罚时,C还莫名其妙的T了一发,另一发也是不应该T的。B连想了两个假做法,然后甚至都实现了,然后过不了样例,再基于这两个才想到了真做法。当时的思路已经有些模糊了,但是确实是写的太慢了,而且\(O(n^2)\)的限制给的也很宽裕,但是我居然还傻乎乎的去先\(O(n^2)......
  • SpingBoot项目Tomcat假死,导致http(openfeign)请求无法响应问题定位
    项目简介:<spring-boot.version>2.3.2.RELEASE</spring-boot.version><spring-cloud.version>Hoxton.SR12</spring-cloud.version>使用docker进行项目部署问题描述:项目中代码中大量使用异步多线程操作,没个异步过程中大量掺杂数据库查询、Redis查询、Feign调用、RabbitMq发送接收......
  • 中电金信:行业智观|2023银行年报分析——金融科技发展新格局(上篇)
    ​​编辑​编辑​编辑​编辑​编辑​编辑​编辑​编辑​编辑​编辑​编辑​编辑​编辑​编辑​......
  • java+saas模式医院云HIS系统源码Java+Spring+MySQL + MyCat融合BS版电子病历系统,支持
    java+saas模式医院云HIS系统源码Java+Spring+MySQL+MyCat融合BS版电子病历系统,支持电子病历四级云HIS系统是一款满足基层医院各类业务需要的健康云产品。该产品能帮助基层医院完成日常各类业务,提供病患预约挂号支持、病患问诊、电子病历、开药发药、会员管理、统计查询、医......
  • 使用 split 命令分割 Linux 文件,使用 cat 合并文件
    一些简单的Linux命令能让你根据需要分割以及重新组合文件,来适应存储或电子邮件附件大小的限制。Linux系统提供了一个非常易于使用的命令来分割文件。在将文件上传到限制大小的存储网站或者作为邮件附件之前,你可能需要执行此操作。要将文件分割为多个文件块,只需使用 split ......
  • Spring Actuator 自定义HealthIndicator
    在SpringActuator实现自定义端点中案例的的基础上,实现自定义HealthIndicator。为什么还要实现HealthIndicator呢?SpringActuator实现自定义端点中案例只是对status的数据进行了监控,至于这个数据是否健康并没有进行评价。实现HealthIndicator就是对自定义监控数据的健康状态根......
  • SpringBoot中application.yml引入多个YML文件
    系列文章目录文章目录系列文章目录前言前言前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。首先,你要了解SpringBoot配置文件加载顺序,加载位置(代码内,Nacos等),当然这......
  • P9750 [CSP-J 2023] 一元二次方程 题解
    题面。直接依照题意模拟即可,注意细节。细节第一注意输出分式时分母为\(1\)不输出,分子为\(0\)直接输出零且不带正负号。第二约分时,\(gcd\)内的两个数应该都是非负实数。第三可以单独输出符号,注意别有多余的符号。第四当方程有两根且均是有理数时,要根据\(2a\)的正......
  • [LitCTF 2023]家人们!谁懂啊,RSA签到都不会 (初级)
    下载task.py看到内容fromCrypto.Util.numberimport*fromsecretimportflagm=bytes_to_long(flag)p=getPrime(512)q=getPrime(512)e=65537n=p*qc=pow(m,e,n)print(f'p={p}')print(f'q={q}')print(f'c={c}')'......
  • 设计规约(Specification)
    转载自[https://zhuanlan.zhihu.com/p/523630664][https://zhuanlan.zhihu.com/p/523630664]并做部分内容上的补充和修改上一节,我们讲了编程语言中、、的概念,尤其详细分析了这三者可变与不可变设计的区别,并导出这一节,我们转向分析编程语言中的以及其对应的,并探究如何定义它们—......