{"problem":{"name":"[Ynoi1999] 56TP","description":{"content":"给包含 $n$ 个顶点的有根树，每个顶点 $i$ 在时刻 $t$ 有权重 $v(t,i)$。 对每个顶点给出 $v(0,i)$，保证对非叶节点 $i$ 有 $v(0,i)=0$，对叶子 $i$ 有 $0\\le v(0,i)\\le n$。 共 $m$ 次询问，每次询问给出 $x,y,t$，问 $x$ 到 $y$ 路径上在时刻 $t$ 的权重的最小值、最大值、和。 对叶子 $i$，有 $v(t,","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10147"},"statements":[{"statement_type":"Markdown","content":"给包含 $n$ 个顶点的有根树，每个顶点 $i$ 在时刻 $t$ 有权重 $v(t,i)$。\n\n对每个顶点给出 $v(0,i)$，保证对非叶节点 $i$ 有 $v(0,i)=0$，对叶子 $i$ 有 $0\\le v(0,i)\\le n$。\n\n共 $m$ 次询问，每次询问给出 $x,y,t$，问 $x$ 到 $y$ 路径上在时刻 $t$ 的权重的最小值、最大值、和。\n\n对叶子 $i$，有 $v(t,i)=v(0,i)$；\n\n对非叶节点 $i$，$t>0$，$v(t,i)$ 是 $i$ 的每个孩子 $j$ 的 $v(t-1,j)$ 的最大值。\n\n## Input\n\n第一行两个整数 $n,m$。\n\n接下来 $n-1$ 行每行一个整数依次表示 $f_2,\\dots,f_n$，其中 $f_i$ 表示节点 $i$ 的父亲，根为 $1$。\n\n接下来 $n$ 行每行一个整数依次表示 $v(0,1),v(0,2),\\dots,v(0,n)$。\n\n接下来 $m$ 行，每行三个整数表示 $x,y,t$。\n\n## Output\n\n输出 $m$ 行，共 $m$ 个整数表示每个询问的答案。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/70a1t3pn.png)\n\n## Note\n\nIdea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078\n\n对于 $100\\%$ 的数据，满足  $1\\le n,m\\le 10^6$，$1\\le f_i\\le i-1$，$0\\le v(0,i)\\le n$，$1\\le x,y,t\\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10147","tags":["1999","O2优化","Ynoi"],"sample_group":[["8 3\n1\n2\n3\n3\n3\n4\n4\n0\n0\n0\n0\n7\n5\n7\n5\n7 5 8\n1 2 8\n8 2 8","7 7 28\n7 7 14\n5 7 26"]],"created_at":"2026-03-03 11:09:25"}}