图论笔记 24-02-18

---

树的重心

删除树上一点，所形成的最大子树最小的那个点是树的重心。

dfs(u,fa){ //若删除u，求最大子树大小
	siz[u]=1;
	mx=0;
	for v:son {
		dfs(v);
		diz[u]+=siz[v];
		siz[v]=max(mx,siz[v]);
	}
	mx=max(mx,n-siz[u]);
}

时间复杂度$O(n)$。

---

性质

1.树的重心如果不唯一，则至多有两个，且这两个重心相邻。
2.以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
3.树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
4.把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
5.在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

dfs() {
	for v:son {
    	求siz和mx;
	}
	ans[u]=u;
	for v:son {
    	重心向上跳
    	if (max(mx[p], siz[u]-siz[p])<=0.5*siz[u]) {
			ans[u]=p;
		}
		else p=fa[p];
	}
}

CF685B 题解

---

点分治

找到树的一个重心，则问题的解可以分为路径经过重心的解和路径不经过中心的解两部分。
1.路径经过重心的解：设重心为树根，用数据结构记录重心到每个节点的路径信息。从中取出根的不同子树中的路径信息组合起来即为路径经过重心的解。
2.路径不经过重心的解：将重心和其关联的边删除，将分割出来的每棵树递归处理即可求出路
径不经过重心的解。

---

树上长度为k的路径

Luogu P3806 P4149

设置两个桶s1，s2，下标为长度，存储有无。
s1：之前子树到$u$点距离；
s2：当前子树到$u$点距离。
处理完每一棵子树，从s2中向s1匹配，寻找距离和为$k$的路径。
然后将s2信息转移到s1中。
若几个子树都没找到，vis[u]=1，对接下来的根节点继续操作。

$f_i$存有无长度为$i$的路径，数值$0$或$1$。
$g_i$存长度为$i$的路径的最小边数。
$a_i$存子树中的路径长度，用于精准清空。
$vis_u$表示$u$是否作为重心被删除了。
$dis_v$表示从$u$到$v$的距离。
$q_i$结构体，存路径距离dis和边数cnt。

新的子树中，把每一个点到$u$的距离都算一遍，长度+边数。
遍历每一条边，凑到$k$后，更新答案ans=min(ans, q[j].cnt+g[k-q[j].dis])。
每一次更新完，信息放到桶里，继续下一个子树。

dfs(u) {
	for v:son {
		dfs(dis[v]);
		for v:路径 {
			ans=...
		}
		for v:路径 {
			更新桶
		}
	}
	for (j=0; j<路径个数; ++j) {
		f[a[j]]=0, g[a[j]]=0; //精准清空，
	}
}

求重心

//全局
weight //重心作用大小
root //重心位置
dfsrt() {
	//n-siz[u]换成weight-siz[u]
}

Luogu P3806 题解
Luogu P4149 题解

---

Luogu P5306

$w_i$：点前缀和，能提供的油量。
$d_i$：边前缀和，需要的油量。
$x$：到顶上后的剩余油量。
对于路径上的两个点$i,\ j$：
上行阶段满足$w_i-w_j\ge d_i-d_j$，变换得到$w_i-d_i\ge w_j-d_j$，记录沿途$max$值，记录存储于$s_1$。
下行阶段$x+w_{fa_j}\ge d_j$，变换得到$x+w_{fa_j}-d_j\ge0$，记录沿途$min$值，记录存储于$s_2$。
由于不知道会剩余多少，将所有$min$值求出扔到$s_2$后与$s_1$匹配，双指针。
Luogu P5306 题解