题意:
给你一棵树,一开始每个点都是白色的,现在你要将点一个一个涂黑,一开始你可以任选一个点,但是之后你需要在黑的点旁边选点。你每次涂黑所得到的值是与你选择的点相邻的白色区块的大小(包括它本身),问你最终得到的值最大是多少。
题解:
稍微模一下就可以发现一定是从某个叶子结点往里面涂色是最优的,因为中间开始的话你就讲它分成多个块了,就不会是最优的。那么我们用dp[i][1]表示到第i个点顺着走下去得到的值是多少,dp[i][1]表示到第i个点逆着回来得到的值是多少。
那么dp[i][1]就等于它儿子的数量+dp[儿子][1],dp[i][0]要枚举儿子节点选择出最优的情况,
dp[ne][0]+dp[x][1]-son[x]-dp[ne][1]+son[1]-son[ne]
也就是儿子回来的最大值加上从它开始dfs下去的值-当前儿子的值-一开始加在dp[x][1]上的儿子数量+从它开始除了当前儿子数量的点的数量。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
ll son[N],dp[N][2];
struct node
{
int to,next;
}e[N*2];
int cnt,head[N];
void add(int x,int y)
{
e[cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt++;
}
void fson(int x,int fa)
{
son[x]=1;
for(int i=head[x];~i;i=e[i].next)
{
int ne=e[i].to;
if(ne==fa)
continue;
fson(ne,x);
son[x]+=son[ne];
}
}
void dfs(int x,int fa)
{
dp[x][1]=son[x];
dp[x][0]=son[1]-son[x]+1;
for(int i=head[x];~i;i=e[i].next)
{
int ne=e[i].to;
if(ne==fa)
continue;
dfs(ne,x);
dp[x][1]+=dp[ne][1];
}
for(int i=head[x];~i;i=e[i].next)
{
int ne=e[i].to;
if(ne==fa)
continue;
dp[x][0]=max(dp[x][0],dp[ne][0]+dp[x][1]-son[x]-dp[ne][1]+son[1]-son[ne]);
}
}
int main()
{
int n,x,y;
memset(head,-1,sizeof(head));
scanf("%d",&n);
for(int i=1;i<n;i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x);
fson(1,0);
dfs(1,0);
printf("%lld\n",max(dp[1][0],dp[1][1]));
return 0;
}