当前位置:网站首页>Recent public ancestor offline practice (tarjan)
Recent public ancestor offline practice (tarjan)
2022-07-01 22:30:00 【Zqchang】
List of articles
Online and offline
Online and offline are generally for questions that are asked
Online practice : Every time I read a question , You can calculate an answer immediately , Then the output
Offline approach : We must first read all the questions in a unified way , Then after unified calculation , Then output all queries in a unified way
tarjan O(n + m)
n It's the number of nodes ,m Is the number of inquiries
The essence is to optimize the upward marking method
Upward marking method
See an online practice for details
In the depth first traversal process, all points are divided into three categories
1. It's been traversed , And back to the point , Searched , And the subtree was searched
2. Branch being searched
3. Points that have not been searched
Suppose you search from left to right , It forms such a tree. Green is the first , Red is the second , That is, a path , The others are the third
For the point being searched , Let's look for related questions , You can see from the picture above , Current inquiry point x And the common ancestor of the green part are the general points of the path , Because the subtree at the midpoint of the path can be merged into that point , Finally, when we seek common ancestors , Just look at the point to which that point is merged , It can be realized by combining and searching sets , This is to find the ancestor node
such , Each point will be traversed only once , It will only be merged once , For each query, it will only be queried once
The main idea
When we traverse the current branch , For the common ancestor of all nodes related to this point , We can find out , If this point has been traversed , The common ancestor of the whole subtree is the point in the path , That is, the root node of the subtree , That is, after traversing a point every time , You can merge the current point directly into the root node , When we look up , You can directly check who is the representative element of the current element in the parallel search set , This representative element is its common ancestor
Pay attention to when to merge , That is, after the backtracking , Then merge it into the parent node
Example
distance
The meaning of the question is to ask for the distance between two points
The method is shown in the figure , Calculate the distance to the root node , Subtract twice the distance of the common ancestor
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define PII pair<int, int>
const int N = 1e4 + 10;
#define x first
#define y second
vector<PII> v[N];
int n, m, a, b, k;
int dist[N];// Store the distance from each point to the root node
int p[N];
int res[N * 2];// Save the answer
int st[N];
vector<PII> query[N]; // first Another query save point ,second Save query number
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void dfs(int u, int fa)
{
for(auto i : v[u])
{
if(i.x == fa) continue;
dist[i.x] = dist[u] + i.y;
dfs(i.x, u);
}
}
void tarjan(int u)
{
st[u] = 1;
for(auto i : v[u])
{
if(!st[i.x])
{
tarjan(i.x);
p[i.x] = u;
}
}
for(auto i : query[u])
{
if(st[i.x] == 2)// Check whether another point has been traced , If you haven't looked back, jump
{
int anc = find(i.x);
res[i.y] = dist[u] + dist[i.x] - dist[anc] * 2;
}
}
st[u] = 2;
}
signed main()
{
cin >> n >> m;
for(int i=1; i<=n-1; i++)
{
cin >> a >> b >> k;
v[a].push_back({
b, k});
v[b].push_back({
a, k});
}
for(int i=1; i<=m; i++)
{
cin >> a >> b;
if(a != b)
{
query[a].push_back({
b, i});
query[b].push_back({
a, i});
}
}
for(int i=1; i<=n; i++) p[i] = i;
dfs(1, -1);
tarjan(1);
for(int i=1; i<=m; i++) cout << res[i] << endl;
return 0;
}
边栏推荐
- ICML2022 | 基于元语义正则化的介入性对比学习
- Manually implement function isinstanceof (child, parent)
- EasyExcel 复杂数据导出
- 指标陷阱:IT领导者易犯的七个KPI错误
- Copy ‘XXXX‘ to effectively final temp variable
- #yyds干货盘点# 解决名企真题:扭蛋机
- Unity uses SQLite
- Burpsuite simple packet capturing tutorial [easy to understand]
- 《QTreeView+QAbstractItemModel自定义模型》:系列教程之三[通俗易懂]
- [monomer] recommended configuration of streaming information i-bpsv3 server
猜你喜欢
In the past 100 years, only 6 products have been approved, which is the "adjuvant" behind the vaccine competition
Sonic cloud real machine learning summary 6 - 1.4.1 server and agent deployment
从零开始学 MySQL —数据库和数据表操作
首席信息官对高绩效IT团队定义的探讨和分析
AIDL基本使用
Little p weekly Vol.11
焱融看 | 混合云时代下,如何制定多云策略
MySQL之MHA高可用配置及故障切换
mysql 学习笔记-优化之SQL优化
BlocProvider 为什么感觉和 Provider 很相似?
随机推荐
mysql 学习笔记-优化之SQL优化
Smart micro mm32 multi-channel adc-dma configuration
都能看懂的LIS(最长上升子序列)问题[通俗易懂]
MIT|256KB 内存下的设备上训练
《QTreeView+QAbstractItemModel自定义模型》:系列教程之三[通俗易懂]
基于三维GIS的不动产管理应用
【深度学习】利用深度学习监控女朋友的微信聊天?
上半年暂停考试要补考?包含监理工程师、建筑师等十项考试
An operation tool used by we media professionals who earn 1w+ a month
Qtreeview+qabstractitemmodel custom model: the third of a series of tutorials [easy to understand]
linux下清理系统缓存并释放内存
MySQL系列之事务日志Redo log学习笔记
CNN卷积神经网络原理讲解+图片识别应用(附源码)[通俗易懂]
【juc学习之路第9天】屏障衍生工具
信标委云原生专题组组长,任重道远!
Manually implement function isinstanceof (child, parent)
BlocProvider 为什么感觉和 Provider 很相似?
News classification based on LSTM model
PCB plug hole technology~
plantuml介绍与使用