درختی داریم که $n$ راس دارد. در هر مرحله میتوانیم به ازای هر مولفه از این درخت دقیقا یکی از ۲ کار زیر را انجام دهیم.
دقت کنید که در یک مرحله میتوان روی دو مولفه کار متفاوتی انجام داد. ثابت کنید: