换根DP学习笔记

标签：dfs rep LL 笔记 DP 换根 dp define

啊啊啊啊啊啊啊啊啊啊啊啊画图累死我了

额，这不菜根快乐DP（根）吗

换根DP，即换根树形DP

平常树形DP指定一个根，但万一邪恶出题人让你求多个点为根的情况呢？

你们可能会想：多跑几遍不就好了！

不可以的，直接TLE。

这有个树，B是A之后的树根（拎上去）：

B成为树根后：

画风突然转变

但是！其实有些没变！

只需要处理一点点就好啦~

直接开题来学：https://www.luogu.com.cn/problem/CF1324F

Let me give you an example:（我英语不好别笑我）

（图中的数左边是白个数，右边是黑）

我就不算结果了哈我很懒

以A为根时，A的两个子树的结果到了现在都可以用！（造福...祖先？）

B左子树也可以用！

把A的原来的最左子树（不太严谨意思到了就行）删掉（跟B是一样的）

再处理A和B

就这样，超级简单！

代码：

#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}
LL n;
LL a[200010],dp[200010],sum[200010];
vector<LL>g[200010];
void dfs(LL v,LL p)
{
	dp[v]=a[v];
	for(auto u:g[v])
	{
		if(u==p)continue;
		dfs(u,v);
		dp[v]+=max(0LL,dp[u]);
	}
}
void sfd(LL v,LL p)
{
	sum[v]=dp[v];
	for(auto u:g[v])
	{
		if(u==p)continue;
		dp[v]-=max(0LL,dp[u]);
		dp[u]+=max(0LL,dp[v]);
		sfd(u,v);
		dp[u]-=max(0LL,dp[v]);
		dp[v]+=max(0LL,dp[u]);
	}
}
int main()
{
	cin>>n;
	rep(i,1,n,1)
	{
		cin>>a[i];
		if(!a[i])a[i]=-1;
	}
	rep(i,1,n-1,1)
	{
		LL u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	sfd(1,0);
	rep(i,1,n,1)cout<<sum[i]<<' ';
	return 0;
}

https://www.luogu.com.cn/problem/CF1187E

这题还挺简单的

因为，拿脑子想想可以发现，确定第一个点后，后面选点的顺序就不影响权值了

为啥？读者自证不难

那就变成了第一个选哪个最好

直接就 换根DP（唉，不是两个字），启动！

用 \(g_x\) 表示先选x能得到的权值

咋转移？

拿眼睛看可以得出：

\[g_y=n+\left ( n-size_y \right ) +\sum_{i\in son_x|i\neq y}^{} f_i+\sum_{i\in son_y}^{} f_i \]

中间过程不写了

最终可以推出

\[g_y=g_x+n-2\times size_y \]

哦对了，\(f_x\) 表示 \(x\) 的子树对它的贡献

代码：

#include<bits/stdc++.h>
#define N 200010
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
using namespace std;
LL n,s[N],f[N],g[N],mc,u,v;
vector<LL>e[N];
void dfs(LL u,LL fa)
{
	s[u]=1;
	for(LL i=0;i<e[u].size();i++)
	{
		LL v=e[u][i];
		if(v==fa)continue;
		dfs(v,u);
		s[u]+=s[v];
		f[u]+=f[v];
	}
	f[u]+=s[u];
}
void sfd(LL u,LL fa)
{
	if(u!=1)
	{
		g[u]=g[fa]+n-s[u]*2;
		mc=max(mc,g[u]);
	}
	for(LL i=0;i<e[u].size();i++)
	{
		LL v=e[u][i];
		if(v==fa)continue;
		sfd(v,u);
	}
}
int main()
{
	cin>>n;
	rep(i,1,n-1,1)
	{
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	mc=g[1]=f[1];
	sfd(1,0);
	cout<<mc<<endl;
	return 0;
}

https://www.luogu.com.cn/problem/P3478

更简单了

思路不写了，转移自己推去（手酸）

代码：

#include<bits/stdc++.h>
#define N 1000010
#define LL long long
#define rep(i,a,b,g) for(int i=a;i<=b;i+=g)
using namespace std;
struct ed
{
	LL u,v,ne;
}e[2*N];
LL d[N];
LL o,h[4*N],s[N],n,dw[N],up[N],f[N],u,v;
void add(LL u,LL v)
{
	e[++o]=(ed){u,v,h[u]};
	h[u]=o;
}
void dfs(LL u,LL fa)
{
	s[u]=1;
	for(LL i=h[u];i;i=e[i].ne)
	{
		LL v=e[i].v;
		if(v==fa)continue;
		f[v]=u;
		d[v]=d[u]+1;
		dfs(v,u);
		s[u]+=s[v];
		dw[u]+=dw[v]+s[v];
	}
}
void sfd(LL u)
{
	if(u!=1)
	{
		up[u]=up[f[u]]+dw[f[u]]-dw[u]-2*s[u]+n;
	}
	for(LL i=h[u];i;i=e[i].ne)
	{
		LL v=e[i].v;
		if(v==f[u])continue;
		sfd(v);
	}
}
int main()
{
	cin>>n;
	rep(i,1,n-1,1)
	{
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	sfd(1);
	LL mc=0,t;
	rep(i,1,n,1)
	{
		if(up[i]+dw[i]>mc)mc=up[i]+dw[i],t=i;
	}
	cout<<t<<endl;
	return 0;
}

然后树上依赖背包要多练。

标签：dfs,rep,LL,笔记,DP,换根,dp,define
From： https://www.cnblogs.com/cppom/p/-/gengengengen