{"problem":{"name":"[EC Final 2022] Coloring","description":{"content":"You are given $n$ elements numbered from $1$ to $n$. Element $i$ has value $w_i$ and color $c_i$. Each element also has a pointer $a_i$ to some other element. Initially, the color of element $s$ is $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9716"},"statements":[{"statement_type":"Markdown","content":"You are given $n$ elements numbered from $1$ to $n$. Element $i$ has value $w_i$ and color $c_i$. Each element also has a pointer $a_i$ to some other element.\n\nInitially, the color of element $s$ is $1$, while the color of all the other elements is $0$. More formally, $c_s=1$ and $c_i=0$ for all $i\\neq s$ $(1 \\le i \\le n)$.\n\nYou can perform the following operation for any number of times:\n\n- Assign $c_i\\leftarrow c_{a_i}$ at a cost of $p_i$.\n\nYour score is equal to the sum of values of all the elements with color $1$ after the operations minus the sum of costs of the operations.\n\nFind the maximum possible score you can obtain.\n\n## Input\n\nThe first line contains two integers $n,s$ ($1 \\leq s\\le n \\leq 5\\times 10^3$) $-$ the number of elements and the element with color $1$ initially.\n\nThe second line contains $n$ integers $w_1,w_2,\\dots,w_n$ ($-10^9\\le w_i\\le 10^9$) $-$ the value of the elements.\n\nThe third line contains $n$ integers $p_1,p_2,\\dots,p_n$ ($0\\le p_i\\le 10^9$) $-$ the cost of changing the color of each element.\n\nThe fourth line contains $n$ integers $a_1,a_2,\\dots,a_n$ ($1\\le a_i\\le n$, $a_i\\neq i$).\n\n## Output\n\nOutput one integer representing the answer in one line.\n\n[samples]\n\n## Note\n\n(There won’t be extra line breakers \nin the actual test cases.)\n\nIn the first sample, you can successively perform the following operations:\n\n- Assign $c_2\\leftarrow c_{a_2}$ at a cost of $p_2$, then $c=[1,1,0]$;\n- Assign $c_1\\leftarrow c_{a_1}$ at a cost of $p_1$, then $c=[0,1,0]$;\n- Assign $c_3\\leftarrow c_{a_3}$ at a cost of $p_3$, then $c=[0,1,1]$;\n- Assign $c_2\\leftarrow c_{a_2}$ at a cost of $p_2$, then $c=[0,0,1]$.\n\nAfter the operations, only the color of element $3$ is $1$, so your score is equal to $w_3-(p_2+p_1+p_3+p_2)=1$. It can be shown that it is impossible to obtain a score greater than $1$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9716","tags":["动态规划 DP","2022","O2优化","基环树","ICPC","EC Final"],"sample_group":[["3 1\n-1 -1 2\n1 0 0\n3 1 2","1"],["10 8\n36175808 53666444 14885614 -14507677 \n-92588511 52375931 -87106420 -7180697 \n-158326918 98234152\n17550389 45695943 55459378 18577244 \n93218347 64719200 84319188 34410268 \n20911746 49221094\n8 1 2 2 8 8 4 7 8 4","35343360"]],"created_at":"2026-03-03 11:09:25"}}