People should only be able to dig out stumps inside their own tribe area, and the trees shouldn't grow back if the stump is removed.
@mrcalhou: 24 hours was only a guesstimation of course It can be more or less, and the respawn should be random inside the given time frame, be it 24-48 hours (only an example). So a tree could regrow 25 hours after it was cut, but it might happen that it only regrow after 47 hours.