LCA与树上DP

2024-10-19 17:44:13

LCA

倍增

f[i][j]代表i的2^j级父亲

f[i][j]=f[f[i][j-1]][j-1]

有了f数组，如何计算“u向上跳k步到达哪个点”？

对k作二进制分解，枚举所有二进制位。

如果第i位为1，那么令u=f[u][i]

O(nlogn) 预处理

	for(int i=1;i<=n;i++)

        f[i][0]=fa[i];

	for(int j=1;j<=20;j++)

		for(int i=1;i<=n;i++)

			f[i][j]=f[f[i][j-1]][j-1];

树上DP

维护树上信息的dp

F[i]代表以i为根的连通块的最大点权和

F[i]+=max(f[j],0)（j是i的儿子）

void dfs(int fa,int x){//DP

	f[x]=v[x];

	for(int i=head[x];i;i=nxt[i]){

		if(to[i]==fa)

			continue;

		dfs(x,to[i]);

		f[x]+=max(f[to[i]],0);

	}

	ans=max(ans,f[x]);

}

最新文章

热门文章