D题：树形DP
题意：给定一棵树，树上每个节点都有权值，断开若干条边，使树变成若干个连通块，定义每个连通块的贡献为连通块内最大点权\(-\)最小点权。算出总贡献和\((ans)\)，要求和最大。
观察：考虑一个连通块，发现对连通块有贡献的仅为最大最小点权所在的点，其他节点贡献为\(0\)，考虑其他节点能不能删去？发现可以，只保留两个关键节点所在的链，其他节点从联通块中断开，对\(ans\)总是不劣(删去的节点要么不会产生贡献，要么会产生正贡献)。继续思考，发现这条链的两个端点应该是关键节点，关键节点外延申到的点也可以断开，对\(ans\)的贡献也是不劣的(同理)。故最优划分应该是若干条链，链的端点点权在链中是最值；不能和其他点组成链的点应该最后是孤立的，对\(ans\)没有贡献。
考虑状态：根据关键观察，每个节点要么是链的最大值，要么是最小值，或者链的中间节点，或者是孤立的点。但是考虑点的状态去设计\(dp\)不太好设计，我们发现每条链也有一些状态，比如在\(dfs\)的过程中一条链要么已经包含两个最值，成为完全状态，要么有最大值缺少最小值，有最小值缺少最大值，后两种情况链都需要继续延申。
尝试设计\(dp\):
- \(dp[u][0]\): 表示节点\(u\)所在的链已经到达完全状态了，此时该子树的贡献；
- \(dp[u][1]\)：表示节点\(u\)所在的链有最大值没有最小值；
- \(dp[u][2]\): 表示节点\(u\)所在的链有最小值没有最大值
设计状态转移：
- 对\(dp[u][0]\):如果\(u\)所在的链已经达到完全状态了，对应的\(u\)的节点状况有哪些？\(u\)可以是一条链的最大值，也可以是最小值，可以是中间值吗?显然可以，比如这条链的最大值在一个\(u\)的一个子树，最小值在\(u\)的另外一个子树，而节点\(u\)作为整个子树的根，肯定就是链的中间值。当然也可以是孤立的点。
\((1)\)如果是最大值：需要从\(u\)的子树中选择一个作为放链的子树，其他子树应该都是完全状态，只有这一个子树中的链不完全且延申到\(u\)结束。\(dp[u][0]=\sum_{1}^{e[u].size()\&\&i\neq j}(dp[i][0])+dp[j][2]+a[u]=\sum(dp[i][0])-dp[j][0]+dp[j][2]+a[u]\);
\((2)\) 如果是最小值：同理\(dp[u][0]=\sum(dp[i][0])-dp[j][0]+dp[j][1]-a[u]\);
\((3)\)如果是中间值：两个子树中有两条链不完全。\(dp[u][0]=\sum(dp[i][0])-dp[j][0]-dp[k][0]+dp[j][1]+dp[k][2]\);
\((4)\)如果是孤立的点：那么他的子树肯定是完全状态，不是完全状态就一定会延申到它，他就不是孤立的点。有\(dp[u][0]=\sum(dp[i][0])\); - 对\(dp[u][1]\):\(u\)的子树中选一个作为放不完全链的子树，其他子树一定是完全状态。有\(dp[u][1]=\sum(dp[i][0])-dp[j][0]+dp[j][1]\);这种情况下链不完全，是需要继续延申的，除了这种\(u\)是链的中间点，链的终点再\(u\)的上面之外，\(u\)也可能是链的起点\(dp[u][1]=\sum(dp[i][0])+a[u]\)
- 对\(dp[u][2]\):同理\(dp[u][2]=\sum(dp[i][0])-dp[j][0]+dp[j][2]\)或者\(dp[u][2]=\sum(dp[i][0])-a[u]\);
思考怎么写：更新状态时始终保证状态值最优即可，对于一些求和项可以先\(dfs\)算出，然后再遍历一遍子节点更新状态。时间复杂度：\(O(能过)\)，反正不是多测,每个节点最最多被搜两次，应该\(O(n)\)，退化成链也能过的存在