F. Weights Assignment For Tree Edges Problem solving report

label ： graph theory , Undirected graph

Topic link

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 .