{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003eCho một cây có $$$n$$$ nút được đánh số từ $$$1$$$ đến $$$n$$$. Mỗi nút $$$i$$$ có một giá trị kèm theo là $$$V_i$$$.\u003c/p\u003e\u003cp\u003eNếu đường đi đơn giản từ $$$u_1$$$ đến $$$u_m$$$ bao gồm $$$m$$$ nút, tức là $$$u_1 \\rightarrow u_2 \\rightarrow u_3 \\rightarrow \\dots u_{m-1} \\rightarrow u_{m}$$$, thì hàm xen kẽ $$$A(u_{1},u_{m})$$$ được định nghĩa là $$$A(u_{1},u_{m}) \u003d \\sum\\limits_{i\u003d1}^{m} (-1)^{i+1} \\cdot V_{u_{i}}$$$. Một đường đi cũng có thể không có cạnh, tức là $$$u_{1}\u003du_{m}$$$.\u003c/p\u003e\u003cp\u003eTính tổng của các hàm xen kẽ của tất cả các đường đi đơn giản duy nhất. Lưu ý rằng các đường đi được điều chỉnh: hai đường đi được coi là khác nhau nếu các đỉnh bắt đầu khác nhau hoặc các đỉnh kết thúc khác nhau. Câu trả lời có thể lớn nên tính nó theo modulo $$$10^{9}+7$$$.\u003c/p\u003e\n"}},{"title":"Input","value":{"format":"MD","content":"\u003cp\u003eDòng đầu tiên chứa một số nguyên $$$n$$$ $$$(2 \\leq n \\leq 2\\cdot10^{5} )$$$ — số lượng đỉnh trong cây.\u003c/p\u003e\u003cp\u003eDòng thứ hai chứa $$$n$$$ số nguyên cách nhau bởi dấu cách $$$V_1, V_2, \\ldots, V_n$$$ ($$$-10^9\\leq V_i \\leq 10^9$$$) — giá trị của các nút.\u003c/p\u003e\u003cp\u003eCác dòng tiếp theo $$$n-1$$$ dòng mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách $$$u$$$ và $$$v$$$ $$$(1\\leq u, v\\leq n, u \\neq v)$$$ chỉ định một cạnh giữa các đỉnh $$$u$$$ và $$$v$$$. Đảm bảo rằng đồ thị được cho là một cây.\u003c/p\u003e\n"}},{"title":"Output","value":{"format":"MD","content":"\u003cp\u003eIn ra tổng tổng của các hàm xen kẽ của tất cả các đường đi đơn giản duy nhất theo modulo $$$10^{9}+7$$$.\u003c/p\u003e\n"}},{"title":"Examples","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n-4 1 5 -2\n1 2\n1 3\n1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e40\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e8\n-2 6 -4 -4 -9 -3 -7 23\n8 2\n2 3\n1 4\n6 5\n7 6\n4 7\n5 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"\u003cp\u003eXem xét ví dụ đầu tiên.\u003c/p\u003e\u003cp\u003eMột đường đi đơn giản từ nút $$$1$$$ đến nút $$$2$$$: $$$1 \\rightarrow 2$$$ có hàm xen kẽ bằng $$$A(1,2) \u003d 1 \\cdot (-4)+(-1) \\cdot 1 \u003d -5$$$.\u003c/p\u003e\u003cp\u003eMột đường đi đơn giản từ nút $$$1$$$ đến nút $$$3$$$: $$$1 \\rightarrow 3$$$ có hàm xen kẽ bằng $$$A(1,3) \u003d 1 \\cdot (-4)+(-1) \\cdot 5 \u003d -9$$$.\u003c/p\u003e\u003cp\u003eMột đường đi đơn giản từ nút $$$2$$$ đến nút $$$4$$$: $$$2 \\rightarrow 1 \\rightarrow 4$$$ có hàm xen kẽ là $$$A(2,4) \u003d 1\n"}}]}