题意

小 O 有一棵树,树上的每一条边都有一个权值 $w$, 他现在想要选择其中一个一定价值的物品, 从 $1$ 号点开始,每个点最多只能经过一次,小 O 想知道最多可以拿到多少价值的物品。

输入

第一行输入一个整数 $n (2 \leq n \leq 10^5)$, 表示树上的点数。

思路:树上dp 考虑对于1号点,如果他有至少两个子树，那么我们一定是先进入其中一个，返回来以后再进入另外一个。

这里假如先进入的是A子树,后进入的是B子树.那么对于A子树来说，我们一定要返回到1号点，所以我们的任务就是在A子树里找一条到叶子的最大权值和。对于B子树来说，我们不一定要返回到1号点，所以问题化解。

学过递归的人应该会有感觉，这种大问题化成小问题的结构可以用递归，然后我们可以记忆化它，也就是动态规划的思路。

由于对于每颗子树可能都有两种情况（例如上面提到的A,B子树），所以定义: dp[i][0] 代表从i出发，需要返回到i的父节点的最大价值

dp[i][1] 代表从i出发，不需要返回到i的父节点的最大价值