当前位置:网站首页>F. Weights assignment for tree edges problem solving Report
F. Weights assignment for tree edges problem solving Report
2022-07-05 15:25:00 【wch(】
F. Weights Assignment For Tree Edges Problem solving report
label : graph theory , Undirected graph
The question :
The problem is quite long , It took me half an hour to understand , The most important thing is patience .
The title first gives a sequence b Count into parent node , Such as b[1]=2, That node 2 Is the node 1 The father node of ,b[2]=2, node 2 yes 2 The father node of , That is to say, nodes 2 It's the root node of the tree .
And then give a p Nodes sort each node ,p[1]=3 That is, node 3 Number one .
use dist The array counts the distance from each point to the root node , Then let's assign a value to the edge weight , Guarantee dist[pi]<dist[pi+1], That is, the lower the ranking, the farther the distance from the point to the root node .
Their thinking
After understanding the meaning of the topic, you can find that the topic is not so difficult .
For a given arrangement p, If there is a node whose parent node ranks lower than that node , dist[ Parent node ]>dist[ The node ], Obviously illegal .
We use it ans Array to include edge weights . To meet the conditions of the topic dist[pi]<dist[pi+1], It can be set by yourself
dist[pi]+1=dist[pi+1];
Then the key code can be obtained to calculate the edge weight .
ans[p[i]] = dist[p[i - 1]] - dist[b[p[i]]] + 1;
dist[p[i]] = dist[b[p[i]]] + ans[p[i]];
Code implementation
#include <iostream>
using namespace std;
const int N = 2 * 1e5 + 50;
int b[N], p[N], dist[N], ans[N];
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int fa = 0;
for (int i = 1; i <= n; i++) {
cin >> b[i];
if (b[i] == i) fa = i;
}
for (int i = 1; i <= n; i++)
cin >> p[i];
for (int i = 1; i <= n; i++)
ans[i] = dist[i] = -1;// Mark the array as -1, Indicates that it has not been marked
int f = 1;
if (p[1] != fa) f = 0;
else
{
ans[p[1]] = 0, dist[p[1]] = 0;
for (int i=2;i<=n;i++)
{
if (dist[b[p[i]]]==-1) { f = 0; break; }
// If the parent node has not been assigned , It indicates that the parent node is behind this node , Illegal array
ans[p[i]] = dist[p[i - 1]] - dist[b[p[i]]] + 1;
dist[p[i]] = dist[b[p[i]]] + ans[p[i]];
}
}
if (f == 0) cout << -1 << endl;
else {
for (int i=1;i<=n;i++) cout << ans[i] << " ";
cout << endl;
}
}
return 0;
}
Ah ha ha ha , My task is finished .
边栏推荐
- 做研究无人咨询、与学生不交心,UNC助理教授两年教职挣扎史
- episodic和batch的定义
- 计算中间件 Apache Linkis参数解读
- Visual task scheduling & drag and drop | scalph data integration based on Apache seatunnel
- qt creater断点调试程序详解
- Bugku easy_ nbt
- Detailed explanation of QT creator breakpoint debugger
- Live broadcast preview | how to implement Devops with automatic tools (welfare at the end of the article)
- Ctfshow web entry information collection
- The difference between SQL Server char nchar varchar and nvarchar
猜你喜欢
随机推荐
Bugku cyberpunk
Calculate weight and comprehensive score by R entropy weight method
mapper.xml文件中的注释
社区团购撤城“后遗症”
Huiyuan, 30, is going to have a new owner
Bugku's Eval
爱可可AI前沿推介(7.5)
Cartoon: what are the attributes of a good programmer?
漫画:程序员不是修电脑的!
Creation and optimization of MySQL index
如何将 DevSecOps 引入企业?
No one consults when doing research and does not communicate with students. UNC assistant professor has a two-year history of teaching struggle
I spring web upload
First PR notes
JS topic - console log()
Bugku easy_ nbt
episodic和batch的定义
Common PHP interview questions (1) (written PHP interview questions)
Dark horse programmer - software testing -10 stage 2-linux and database -44-57 why learn database, description of database classification relational database, description of Navicat operation data, de
Anti shake and throttling