Ağacda intervallar

Verilmiş ağac n zirvədən və müvafiq olaraq n − 1 kənardan ibarətdir. Zirvələr 1, 2, ..., n və kənarlar 1, 2, ..., n − 1 nömrələnmişdir. i-ci kənar u[i] və v[i] zirvələrini birləşdirir.

L, R (1 ≤ L ≤ R ≤ n) ədədləri üçün f(L, R) funksiyasını aşağıdakı kimi təyin edək:

• S - L-dən R-ə qədər nömrələnmiş zirvələr çoxluğu olsun. f(L, R) funksiyası yalnız S zirvələr çoxluğundan və hər iki ucu S-ə aid olan kənarlardan ibarət alt qrafda əlaqəli komponentlərin sayını göstərir.

Aşağıdakı ifadənin qiymətini hesablayın:

Giriş məlumatları

Birinci sətir n ədədini (1 ≤ n ≤ 2 * 10^5) ehtiva edir. Növbəti n − 1 sətirin hər biri qrafda bir kənar olan iki zirvəni (u[i], v[i]) (1 ≤ u[i], v[i] ≤ n) ehtiva edir.

Çıxış məlumatları

Cəmin qiymətini çıxış edin.

Nümunə

Altı mümkün cütlük (L, R) var:

L = 1, R = 1 üçün, S = {1}, 1 əlaqəli komponent var.

L = 1, R = 2 üçün, S = {1, 2}, 2 əlaqəli komponent var.

L = 1, R = 3 üçün, S = {1, 2, 3}, S hər bir kənarın hər iki ucunu ehtiva etdiyindən 1 əlaqəli komponent var.

L = 2, R = 2 üçün, S = {2}, 1 əlaqəli komponent var.

L = 2, R = 3 üçün, S = {2, 3}, S kənar 2-nin hər iki ucunu ehtiva etdiyindən 1 əlaqəli komponent var.

L = 3, R = 3 üçün, S = {3}, 1 əlaqəli komponent var.

Bütün qiymətlərin cəmi 7-yə bərabərdir.