Please read the new rule regarding the restriction on the use of AI tools. ×

TunaMayoSandwich's blog

By TunaMayoSandwich, history, 6 hours ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
6 hours ago, # |
  Vote: I like it +7 Vote: I do not like it

Input section says that $$$a_i<i$$$, this indeed means that each node has only children of greater index.

  • »
    »
    5 hours ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Thank you, I should have seen that.