Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

What does it mean for the nodes to be numbered from 1 to n

Правка en2, от TunaMayoSandwich, 2024-09-21 17:27:59

Maybe this is the stupidest question you've ever heard, but what does it mean when a problem states "you are given a generic tree [...] the vertices are numbered from $$$1$$$ to $$$n$$$"? Take for example 2002D2 - DFS Checker (Hard Version), the editorial's solution involves finding the sizes of all subtrees, a task which I intended to solve with a piece of code like this one.

void find_sizes(vector<ll>& tree, vector<ll>& sizes, ll index){
	if(tree[index].empty()){
		sizes[index] = 1;
		return;
	}
	
	for(auto child : tree[index]){
		find_sizes(tree, sizes, child);
		sizes[index] += sizes[child];
	}
}

Then I took a look at the editorial's code as well as this submission 275817652 by Um_nik and they just do something like this.

// Initialise all sizes to 1
for(ll i = n; i >= 2; i--) size[father[i]] += size[i];

But this of course only works if the nodes are ordered from $$$1$$$ to $$$n$$$ meaning that every node can only have children of greater index, if this doesn't hold a trivial counterexample is the tree 1 -> 3 -> 2. Am I going crazy? Again, sorry if this sounds mind-bogglingly stupid, but if I am correct I think the Codeforces jargon should be changed to reflect that the nodes are actually ordered in this case. To me the fact that they are numbered from $$$1$$$ to $$$n$$$ only means that they are labelled that way but they can still be scrambled up. I am ready to be embarrassed if I'm not seeing the obvious.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский TunaMayoSandwich 2024-09-21 17:27:59 8 Tiny change: 'ildren of lower index, ' -> 'ildren of greater index, '
en1 Английский TunaMayoSandwich 2024-09-21 17:19:12 1539 Initial revision (published)