Weights Assignment For Tree Edges 树，拓扑序（1500）

题意 ：

• 给定n个结点的树和序列$b$和$p$，$b_i$表示i结点的父节点，其中$b_{root}=root$，现在要给树上的每个边赋正权值，使得每个结点到根的距离$dis{t}_i$满足p的排序，即如果在p数组中，i点位置在j点前面，则$dis{t}_i<dis{t}_j$
• 如果可行，输出每条边的权值，否则，输出-1

思路 ：

• 因为每条边都赋正值，那么考虑一个结点，它的排名不可能比父节点靠前，也就是说p数组满足拓扑序
• 对于$p=[3,1,2,5,4]$，构造$dis{t}_3=0$（第一个肯定是根结点），$dis{t}_1=2,dis{t}_2=3,...,$满足枚举的顺序，这个是结点到根的距离，只要记录一下父节点到根的距离，相减就是这个边的权值
• 因此，按照p数组的顺序从第一个非根结点开始枚举每个点，如果枚举到的这个点的父节点排名比它低（dist数组值为-1），直接return输出-1，否则，当前这个结点dist数组值为i，ans数组记录这个点到父节点这条边的边权，就是当前这个点到根的距离减去父节点到根的距离

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #include <math.h> using namespace std;typedef long long ll; typedef pair<int, int> PII;#define endl '\n' #define fi first #define se second #define push_back #define rep(i, l, r) for (ll i = l; i <= r; i ++ )const int N = 2e5 + 10;int b[N], p[N]; int ans[N], dist[N]; // ans为i点到父节点的距离，即边权；dist为i点到根结点的距离void solve() {int n; cin >> n;for (int i = 1; i <= n && cin >> b[i]; i ++ );for (int i = 1; i <= n && cin >> p[i]; i ++ );for (int i = 1; i <= n; i ++ ) ans[i] = dist[i] = -1; // 初始化！同时也可以标记该点是否已经被访问过，相对排名ans[p[1]] = 0, dist[p[1]] = 0;for (int i = 2; i <= n; i ++ ){int j = p[i]; // 当前这个点if (dist[b[j]] == -1) return cout << -1 << endl, void();dist[j] = i;ans[j] = dist[j] - dist[b[j]];}for (int i = 1; i <= n; i ++ ) cout << ans[i] << " \n"[i == n]; }int main() {cin.tie(nullptr) -> sync_with_stdio(false);int _;cin >> _;while (_ -- )solve();return 0; } 与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的Weights Assignment For Tree Edges 树，拓扑序（1500）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。