+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امیرحسین و محمدسام درختی پیدا کرده‌اند و به دلیل اعصاب خرابشان دقیقاً نمی‌دانند که چه کاری می‌خواهند با این درخت انجام دهند. ابتدا امیرحسین به رأس $u$ یک مقدار $a_u$ نسبت می‌دهد. می‌دانیم امتیاز $path(u, v)$ برابر است با: \[ \frac{\sum_{w \in \operatorname{path}(u,v)} a_w}{\operatorname{len}(u,v)} \] که در آن $path(u, v)$ کوتاه‌ترین مسیر از رأس $u$ به رأس $v$ است و $len(u, v)$ تعداد رأس‌های موجود در $path(u, v)$ را نشان می‌دهد. در ادامه محمدسام یک عدد $k$ انتخاب می‌کند و سپس در $q$ مرحله مقدار بعضی از رأس‌ها را افزایش می‌دهد. شما باید پس از هر درخواست، در میان تمامی مسیرهایی که حداقل $k$ رأس دارند، بیشترین امتیاز ممکن را پیدا کنید. توجه کنید که هر عملیات روی درختی انجام می‌شود که تمام تغییرات مراحل قبل روی آن اعمال شده است. # ورودی شما باید مسئله را برای $T$ تست‌کیس مستقل حل کنید. در خط اول، عدد $T$ داده می‌شود. برای هر تست‌کیس: - در خط اول دو عدد $n$ و $k$، به‌ترتیب تعداد رأس‌های درخت و عدد انتخابی محمدسام، داده می‌شود. - در خط دوم، $n$ عدد داده می‌شود که مقدار $a_i$ را برای هر رأس مشخص می‌کنند. - در $n-1$ خط بعد، هر خط شامل دو عدد $v_i$ و $u_i$ است که دو سر یال‌های درخت را مشخص می‌کنند. - در خط بعد، عدد $q$ داده می‌شود که تعداد تغییرات را نشان می‌دهد. - در $q$ خط بعد، هر خط شامل دو عدد $v_i$ و $x_i$ است؛ یعنی در این مرحله مقدار رأس $v_i$ به اندازه $x_i$ افزایش می‌یابد. $$1 \leq T \leq 10^5$$ $$1 \leq n \leq 10^5$$ $$1 \leq k \leq 10$$ $$1 \leq q \leq 10^4$$ $$1 \leq a_i, x_i \leq 10^9$$ تضمین می‌شود که مجموع مقادیر $n$ در تمامی تست‌کیس‌ها از $3 \times 10^5$ و مجموع مقادیر $q$ از $3 \times 10^4$ بیشتر نخواهد شد. # خروجی برای هر پرسش، پاسخ را به صورت $A/B$ چاپ کنید، به‌طوری که: $$gcd(A,B)=1$$ # مثال ## ورودی نمونه ۱ ```text 2 6 2 6 16 6 15 5 4 1 2 2 3 2 4 2 5 4 6 2 1 4 3 5 14 1 12 19 9 17 9 10 11 18 9 19 10 14 18 8 1 2 2 3 1 4 1 5 4 6 2 7 7 8 8 9 6 10 6 11 1 12 11 13 3 14 5 10 3 2 8 7 9 5 6 2 1000000000 ``` ## خروجی نمونه ۱ ```text 31/2 31/2 22/1 27/1 27/1 27/1 1000000027/1 ```