Блог пользователя TunaMayoSandwich

Автор TunaMayoSandwich, история, 2 месяца назад, По-английски

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.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
2 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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