{"trustable":true,"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":"HTML","content":"\u003cp\u003e千反田拥有一片农场,上面种有$$$n$$$棵苹果树,分别用$$$1,2,\\dots,n$$$标记,第$$$i$$$棵苹果树有$$$a_i$$$个苹果。它们之间有$$$n-1$$$条双向道路相连。对于所有的$$$i\u0026gt;1$$$,编号为$$$i$$$的苹果树通过一条道路与编号为$$$\\lfloor\\frac{i}{2}\\rfloor$$$的苹果树相连。因此农场的地图也像一棵树一样。\u003c/p\u003e\u003cp\u003e苹果生意兴隆。有$$$m$$$个请求,分别用$$$1,2,\\dots,m$$$标记。对于第$$$i$$$个请求,千反田最多可以卖给顾客$$$c_i$$$个苹果,每个苹果的售价为$$$w_i$$$美元。不幸的是,不同的顾客有不同的偏好。具体来说,对于第$$$i$$$个请求,顾客会给出两个整数$$$u_i$$$和$$$v_i$$$,表示他只接受从地图上编号为$$$u_i$$$的苹果树到编号为$$$v_i$$$的苹果树的最短路径上的苹果(包括$$$u_i$$$和$$$v_i$$$)。\u003c/p\u003e\u003cp\u003e假设地图的根节点是第$$$1$$$个苹果树。令人惊奇的是,$$$u_i$$$总是$$$v_i$$$的祖先或者$$$u_i\u003dv_i$$$。\u003c/p\u003e\u003cp\u003e农场可能无法向每个顾客出售$$$c_i$$$个苹果。请编写一个程序来帮助千反田销售苹果,以最大化他的利润。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含一个整数$$$T(1\\leq T\\leq 1000)$$$,表示测试用例的数量。\u003c/p\u003e\u003cp\u003e在每个测试用例中,第一行有两个整数$$$n,m(1\\leq n,m\\leq 100000)$$$,表示苹果树的数量和请求的数量。\u003c/p\u003e\u003cp\u003e第二行有$$$n$$$个整数$$$a_1,a_2,...,a_n(1\\leq a_i\\leq 10^9)$$$,表示每棵苹果树上的苹果数量。\u003c/p\u003e\u003cp\u003e接下来的$$$m$$$行,每行包含四个整数$$$u_i,v_i,c_i,w_i(1\\leq u_i,v_i\\leq n,1\\leq c_i\\leq 10^9,1\\leq w_i\\leq 10^4)$$$,表示每个请求。保证$$$u_i$$$是$$$v_i$$$的祖先或者$$$u_i\u003dv_i$$$。\u003c/p\u003e\u003cp\u003e保证$$$\\sum n\\leq 10^6$$$和$$$\\sum m\\leq 10^6$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试用例,输出一个整数,表示最大利润。\u003c/p\u003e"}},{"title":"示例 1","value":{"format":"HTML","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\u003e1\n5 3\n2 1 3 1 1\n2 5 2 3\n2 4 2 4\n1 2 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}