In terms of explosives, you could always have the battle take place during a thunderstorm. At the start of each turn, roll a die for each tree (obviously indicate which tree each roll is for).
On a roll of 5, the tree is stuck by lightning and is set on fire, and whatever fire rules you're using (are there any official ones?) are put in effect.
On a roll of 6, the tree is struck with an even more intense lighting bolt, and the tree explodes violently, sending wooden shrapnel flying in all directions.
The explosion damage is determined by the size of the tree's trunk; if it's 1x1 stud, it's a 1d10 explosion; if it's 2x2 studs, it's a 2d10 explosion, and so on and so forth.
The poo ideas are great, too. Maybe they could have air strikes in the form of flocks of birds?