当前位置:网站首页>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 .
边栏推荐
- 【jvm】运算指令
- go学习 ------jwt的相关知识
- 社区团购撤城“后遗症”
- I spring and autumn blasting-2
- Install and configure Jenkins
- Photoshop plug-in - action related concepts - actions in non loaded execution action files - PS plug-in development
- Object. defineProperty() - VS - new Proxy()
- Go learning ----- relevant knowledge of JWT
- The difference between SQL Server char nchar varchar and nvarchar
- 超越PaLM!北大碩士提出DiVeRSe,全面刷新NLP推理排行榜
猜你喜欢
Machine learning notes - gray wolf optimization
Install and configure Jenkins
Photoshop plug-in action related concepts actionlist actiondescriptor actionlist action execution load call delete PS plug-in development
Bugku easy_ nbt
P6183 [USACO10MAR] The Rock Game S
30岁汇源,要换新主人了
"Sequelae" of the withdrawal of community group purchase from the city
把 ”中台“ 的思想迁移到代码中去
Bugku's eyes are not real
1330:【例8.3】最少步数
随机推荐
1330:【例8.3】最少步数
Machine learning notes - gray wolf optimization
Mysql---- function
Anti shake and throttling
华为哈勃化身硬科技IPO收割机
[recruitment position] infrastructure software developer
Mongdb learning notes
Coding devsecops helps financial enterprises run out of digital acceleration
easyOCR 字符識別
MySQL表字段调整
queryRunner. Query method
数据库学习——数据库安全性
Good article inventory
What are CSRF, XSS, SQL injection, DDoS attack and timing attack respectively and how to prevent them (PHP interview theory question)
机器学习笔记 - 灰狼优化
MySQL----函数
Bugku's Eval
MySQL之CRUD
P1451 求细胞数量/1329:【例8.2】细胞
漫画:优秀的程序员具备哪些属性?