每个分支的最大值

难度：T2

【知识点：二叉树遍历】【知识点：递归】

前置知识：孩子数组、空树、对应遍历规则

题目描述

给定一棵合法二叉树，节点编号为 $1$ 到 $n$，根编号为 $root$。左右孩子有区别，编号大小与位置无关；$0$ 表示空孩子，不是节点。保证无环、所有节点属于同一棵树、非根恰好有一个父节点。

每个节点有整数权值 $v_u$，可能为负数。求每个节点的子树内最大权值，包含自己，最后按节点编号从小到大输出这些最大值。

输入格式

第一行给 $n,root$。接下来 $n$ 行，第 $u$ 行给 $lc_u,rc_u$，表示节点 $u$ 的左右孩子。最后一行按编号给出 $n$ 个权值。

输出格式

一行输出题目所求序列，整数之间用空格分隔。

样例输入

7 1
2 3
4 5
0 6
0 0
7 0
0 0
0 0
-1 -2 -3 -4 -5 -6 -7

样例输出

-1 -2 -3 -4 -5 -6 -7

数据范围

$1\le n\le200$，$1\le root\le n$，$0\le lc_u,rc_u\le n$。$-1000\le v_u\le1000$。