【CF1187E】Tree Painting

题目大意：给定一棵 N 个点的树，初始全是白点。要求你做 N 步操作，每一次选定一个与一个黑点相隔一条边的白点，将它染成黑点，然后获得该白点被染色前所在的白色联通块大小的权值。第一次操作可以任意选点，求可获得的最大权值。

题解：对于答案仅由起始点决定的 dp 采用换根法。

发现对于两个相邻的染了黑色的点来说，这两个点染色的先后顺序会对答案产生影响，但是不会对其他点产生影响。同时，可以发现该问题一旦选定了初始点，无论怎样进行染色，答案均相同。因此，考虑采用换根法，需要计算出相邻两个点先后顺序对答案的影响，根据第一个性质，可知仅需要计算第一次两个点对答案的影响即可。画图可知，相邻两点对答案贡献的差值为 \(n-2*sz[v]\)。

代码如下

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int maxn=2e5+10;

typedef long long LL;

int n,sz[maxn];

vector<int> G[maxn];

LL f[maxn],ans;

void dfs1(int u,int fa){

	sz[u]=1;

	for(auto v:G[u]){

		if(v==fa)continue;

		dfs1(v,u);

		sz[u]+=sz[v];

	}

	ans+=sz[u];

}

void dfs2(int u,int fa){

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

	for(auto v:G[u]){

		if(v==fa)continue;

		f[v]=f[u]+n-2*sz[v];

		dfs2(v,u);

	}

}

void read_and_parse(){

	scanf("%d",&n);

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

		int x,y;

		scanf("%d%d",&x,&y);

		G[x].pb(y),G[y].pb(x);

	}

}

void solve(){

	dfs1(1,0);

	f[1]=ans;

	dfs2(1,0);

	printf("%lld\n",ans);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【CF1187E】Tree Painting

最新文章

热门文章