Trees are pretty linear in nature, since the number of edges is always one less than the number of vertices. Furthermore, the absence of cycles can sometimes drastically reduce the computational complexity of otherwise pretty hard problems. For example, the longest path problem is NP-hard for general graphs, but is easily solved in linear time for trees. Many other examples exists, where a graph problem magically becomes doable in constant- or linear-time, just because of the restriction to trees (an example for the constant case being the minimum spanning tree problem). I guess sometimes you could be forced to a linearithmic lower bound, although I'm not completely sure at the time of writing this (but my main question for now lies in the next paragraph).
However, I have struggled for a few weeks to come up with an example of a problem that has to have an $\Omega(n^2)$ bound even when restricting to trees. I suspect these problems may exist, but can't come up with any. Can anyone give me an example, or alternatively give me a proof that all decision problems on trees are decidable in less than quadratic time?
Of course, I assume we are not representing the tree using the adjacency matrix, but rather an adjacency-list or other timesaving data structure.
I also suspect that I might need to explicitly state to consider only tractable problems, since I guess you could come up with halting-type problems for trees otherwise.