当前位置:网站首页>2022牛客多校第三场 A Ancestor
2022牛客多校第三场 A Ancestor
2022-08-05 00:18:00 【Rain Sure】
题目链接
题目大意
给了我们两棵树 A A A和 B B B,然后给了我们 k k k个点,问我们分别在 A A A和 B B B删去其中一个点,使得剩余点在 A A A树中的最近公共祖先的权值大于剩余点在 B B B树中的最近公共祖先的权值。
题解
首先,预处理出来,这 k k k个点的前缀最近公共祖先和后缀最近公共祖先,然后,分别枚举 k k k个点,将该点去掉的最近公共祖先就是 l c a ( p r e [ i − 1 ] , b a c k [ i + 1 ] ) lca(pre[i - 1], back[i + 1]) lca(pre[i−1],back[i+1]),如此便可进行判断。
代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define x first
#define y second
#define int long long
#define endl '\n'
const int inf = 1e9 + 10;
const int maxn = 100010, M = 200010;
const int mod = 1e9 + 7;
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
int key[maxn];
int n, k;
struct Tree
{
int h[maxn], e[M], ne[M], idx;
int v[maxn];
int pre[maxn], back[maxn];
int fa[maxn][20];
int depth[maxn];
Tree()
{
memset(h, -1, sizeof h);
}
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs(int root)
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[root] = 1;
queue<int> q;
q.push(root);
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if(depth[j] > depth[t] + 1) {
depth[j] = depth[t] + 1;
q.push(j);
fa[j][0] = t;
for(int k = 1; k <= 18; k ++) {
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
}
int lca(int a, int b)
{
if(a == 0) return b;
if(b == 0) return a;
if(depth[a] < depth[b]) swap(a, b);
for(int k = 18; k >= 0; k --){
if(depth[fa[a][k]] >= depth[b]) {
a = fa[a][k];
}
}
if(a == b) return a;
for(int k = 18; k >= 0; k --){
if(fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}
void init()
{
bfs(1);
pre[1] = key[1], back[k] = key[k];
for(int i = 2; i <= k; i ++) pre[i] = lca(pre[i - 1], key[i]);
for(int i = k - 1; i >= 1; i --) back[i] = lca(back[i + 1], key[i]);
}
int calc(int x)
{
return v[lca(pre[x - 1], back[x + 1])];
}
}ta, tb;
signed main()
{
IOS;
cin >> n >> k;
for(int i = 1; i <= k; i ++) cin >> key[i];
for(int i = 1; i <= n; i ++) cin >> ta.v[i];
for(int i = 2; i <= n; i ++){
int x; cin >> x;
ta.add(x, i);
}
for(int i = 1; i <= n; i ++) cin >> tb.v[i];
for(int i = 2; i <= n; i ++){
int x; cin >> x;
tb.add(x, i);
}
ta.init();
tb.init();
int res = 0;
for(int i = 1; i <= k; i ++){
int t1 = ta.calc(i), t2 = tb.calc(i);
if(t1 > t2) res ++;
}
cout << res << endl;
return 0;
}
边栏推荐
- How to automatically push my new articles to my fans (very simple, can't learn to hit me)
- The applicable scenarios and common product types of the KT148A electronic voice chip ic solution
- 关于使用read table 语句
- 3. Actual combat---crawl the result page corresponding to Baidu's specified entry (a simple page collector)
- What is next-generation modeling (with learning materials)
- SV 类的虚方法 多态
- Statistical words (DAY 101) Huazhong University of Science and Technology postgraduate examination questions
- 【Valentine's Day special effects】--Canvas realizes full screen love
- 2022 Niu Ke Summer Multi-School Training Camp 5 (BCDFGHK)
- jenkins send mail system configuration
猜你喜欢
随机推荐
LeetCode Hot 100
"Relish Podcast" #397 The factory manager is here: How to use technology to empower the law?
[CVA Valuation Training Camp] Financial Modeling Guide - Lecture 1
SQL association table update
[230]连接Redis后执行命令错误 MISCONF Redis is configured to save RDB snapshots
About I double-checked and reviewed the About staff page, returning an industry question
建模师经验分享:模型学习方法
Mysql_12 多表查询
统计单词(DAY 101)华中科技大学考研机试题
图解 Canvas 入门
Getting started with 3D modeling for games, what modeling software can I choose?
英特尔WiFi 7产品将于2024年亮相 最高速度可达5.8Gbps
三、实战---爬取百度指定词条所对应的结果页面(一个简单的页面采集器)
2022杭电多校第一场 1004 Ball
典型相关分析CCA计算过程
KT148A电子语音芯片ic方案适用的场景以及常见产品类型
在线中文姓名生成工具推荐
ARC129E Yet Another Minimization 题解 【网络流笔记】
How to automatically push my new articles to my fans (very simple, can't learn to hit me)
SQL关联表更新