关于这道题分类的一个技巧
查看原帖
关于这道题分类的一个技巧
105254
Piwry楼主2020/8/29 20:49

挺显然的,不过(也因此?)没人专门提

代码中需要在换根时维护一个 从该结点到该子树内 “关键点” 的最长/次长路径距离

如果这个路径实际上不存在,其实可以设一个负极大值的缺省值,这样在换根时就不用考虑这个路径存在与否了

大概差不多这样子:

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

2020/8/29 20:49
加载中...