CF1442E Black, White and Grey Tree

一、题目

点此看题

二、解法

发现这个东西 \(dp\) 真的不好维护，为了简化问题我们把一个同色的连通块缩成一个点，因为这个连通块内所有点的行为一定平行（老生物了），然后我们手玩可以发现有这样两种比较可行的策略：

• 选取一种颜色直接删除其所有点，然后剩下的点暴力删除，次数是 较小的同色点数\(+1\)
• 把从最外层开始（度数为 \(1\)）把同色点一层一层删掉，设 \(d\) 为直径，次数是 \(\frac{d+1}{2}+1\)

再多玩几组数据发现第一种策略有处理不到的情况（比如两个菊花连一起），但是第二种策略貌似可行。

那么现在我们来证明第二种策略（以下简称策略）最优，考虑数学归纳法，首先第二种方法做链是最优的。然后对于树的情况我们考虑不删叶子将之划分成若干个树，由于归纳到了更小的情况这些树一定策略 \(2\) 更优，现在和直接用策略比较代价变化，发现一次拆分最多让直径之和减少 \(1\)，但是由于多了一棵树就会增加 \(1\) 的代价，发现一定不优，故归纳到了更大的情况。

知道这个策略之后我们决策灰点让直径最小即可，那么这个直接树 \(dp\) 啊，设 \(f[u][i]\) 表示 \(u\) 的颜色为 \(i\) 的最长链，\(g[u][i]\) 表示 \(u\) 颜色为 \(i\)，经过 \(u\) 的最长路径，转移考虑把子树 \(v\) 合并上来：

\[g[u][i]\leftarrow \max(g[u][i],\min(f[u][i]+f[v][j]+(i\not=j))) \]

\[f[u][i]\leftarrow \max(f[u][i],\min(f[v][j]+(i\not=j))) \]

那么 \(r=\max(\min(g[u][i]))\)，时间复杂度 \(O(n)\)

三、总结

简化问题真的很重要，你看着第一步很简单但我就是因为它没做出来，我们可以思考一些显然最优的操作简化问题。

构造最优策略可以先手玩小样例然后选出最有可能最优的策略尝试证明，证明方法有势能证明法，这里我用了归纳法。

尽可能形式地证明我们所直观看到的，以及尽可能直观地看出我们所形式证明过的，这是一种增进智力的练习。不幸，在教学中，并不总有时间来这样做。——波利亚《怎样解题》

为什么会有这样的策略？我的思考是这个策略着重于维护连通性，而第一种策略着重于最大化第一步的收益，在此问题中第一种策略更优，这启示我们推结论的时候可以考虑以贪心最优化某一变量，虽然这样总不一定正确。

#include 
#include 
using namespace std;
const int M = 200005;
const int inf = 0x3f3f3f3f;
int read()
{
	int x=0,flag=1;char c;
	while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
	while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*flag;
}
int T,n,tot,ans,a[M],f[M],dp[M][2];
struct edge
{
	int v,next;
}e[2*M];
void dfs(int u,int fa)
{
	if(a[u]==1) dp[u][0]=0,dp[u][1]=inf;
	else if(a[u]==2) dp[u][0]=inf,dp[u][1]=0;
	else dp[u][0]=dp[u][1]=0;
	int r[2]={0,0};
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
		int g[2]={inf,inf},t[2]={inf,inf};
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
			{
				t[j]=min(t[j],max(r[j],dp[u][j]+dp[v][k]+(j!=k)));
				g[j]=min(g[j],max(dp[u][j],dp[v][k]+(j!=k)));
			}
		memcpy(r,t,sizeof r);
		memcpy(dp[u],g,sizeof dp[u]);
	}
	ans=max(ans,min(r[0],r[1]));
}
void work()
{
	n=read();tot=ans=0;
	for(int i=1;i<=n;i++)
		a[i]=read(),f[i]=0;
	for(int i=1;i