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.