首先不难发现，确定了根以后答案是固定的。设\(sz_i\)表示以1为根的树中，以1为根的子树大小；\(f_i\)表示以1为根的树中，以\(i\)为根的子树得到的最大权值，可以得到转移\[f_u=sz_u+\sum_{v\inson_u}f_v\]然后设\(g_v\)表示先选\(v\)的最大权值，\(v\)的父亲为\(