挺显然的,不过(也因此?)没人专门提
代码中需要在换根时维护一个 从该结点到该子树内 “关键点” 的最长/次长路径距离
如果这个路径实际上不存在,其实可以设一个负极大值的缺省值,这样在换根时就不用考虑这个路径存在与否了
大概差不多这样子:
void dfs(int u, int fa){
p[u] =p2[u] =-0x3f3f3f3f3f3f3f3f;
if(isk[u])
p[u] =0;
/*...*/
}
void dfs2(int u, int fa){
ans[u] =dp[u]*2-p[u];
for(int l =first[u]; l; l =e[l].net)
if(e[l].to != fa){
/*...*/
/*下面就是分两类直接维护*/
ll res;
if(chose[u] == e[l].to)/*路径在新根原子树内就用次大值*/
res =p2[u];
else
res =p[u];
/*分别更新最大次大值*/
if(res+e[l].val > p[e[l].to]){
p2[e[l].to] =p[e[l].to];
p[e[l].to] =res+e[l].val;
chose[e[l].to] =u;
}
else if(res+e[l].val > p2[e[l].to])
p2[e[l].to] =res+e[l].val;
dfs2(e[l].to, u);
}
}
变量名感性理解下X