观察其实就是每个节点可以作为蓝线的中点一次，然后求蓝线的最大权值和。考虑如果是有根的话，可能是son[x]-x-fa[x]这种结构，也可能是son[x]-x-son[x]。应该可以用一个dp[i][0/1/2]的树形dp来解决，但是由于上一场EDU的E的启示，我们可以想到一般这种3个状态，可以从父亲再到儿子的dp，可以用换根dp只需要考虑儿子到父亲的转移，这题也是一样。（3个状态能做，但是转移比较复杂）
考虑dp[x][0/1][t]表示x这个点，有没有作为中点，忽略第t个儿子的答案。（祖先在换根之后也可以是儿子）。我们先考虑有根的时候怎么转移。
- dp[x][0]：每个儿子可以是dp[y][1]+e[i].w，也可以是dp[y][0]，取个max就行。
- dp[x][1]：需要有一个儿子是dp[x][0]（如果都是1那么必须要父亲在儿子之前出现，但是这时候父亲是中点所以必须要在一个儿子后出现，矛盾了）+e[i].w。其他的像dp[x][0]那么转移即可。
然后是换根dp的经典套路：忽略。忽略我们不能全部重新计算，观察一下式子发现基本不变，只有max有可能会变，所以保留最大和次大即可（也是经典的套路）。
换根也不难，父亲到儿子的时候更新为父亲忽略这个儿子的dp，再用父亲的dp来更新儿子不忽略父亲的dp，依次换根就是正确的了，在每个根的时候取个max即可。
Submission：https://uoj.ac/submission/609798
标签：Beads,wires,APIO2014,儿子,忽略,父亲,son,换根,dp From： https://www.cnblogs.com/IceYukino/p/17184669.html