[??记录]AT4133 [ARC097D] Monochrome Cat
command_block
2021-01-12 18:42:47
**题意** ： 给出一棵 $n$ 个点的树，初始时每个点为黑色或白色。
以任意节点开始操作，每轮操作可以选择是否移动到相邻节点，然后将当前所在的节点颜色取反。
求使所有点变为黑色的最小操作次数。
$n\leq 10^5$ ，时限$\texttt{2s}$。
------------
完全不会啊qwq
首先，显然只需要保留全体白色点的虚树。
然后，必须要将这颗树完整遍历一次，但经过每个点的次数随着起止点的选取而变化，不便分析。
不妨先考虑回路，这样，每条边都会被正反各走一次，每个点都恰会被经过度数次。
这样走过之后，标记树上剩余的白点，只需要在此处停留一步就能将其变为黑点。
回路的问题已经解决了，现在考虑起止点的选择。假设选择 $u\rightarrow v$ ，那么可以让 $[u,v)$ 中所有点少经过一次。
- 对于没有标记的点，少经过一次，所以需要停留一回合，没有贡献。
- 对于有标记的点，少经过一次，所以不需要再停留，贡献为 $-2$。
所以，选择一条标记点最多的路径即可。
注意，$v$ 是不包含在路径内的，所以需要特判只有一个白点的情况。
只要有多个白点，叶节点处的白点肯定不是标记点，选出的路径必然可以以两个无标记叶节点为端点。这样，端点在不在路径内就无关紧要了。
最终答案为 $2\times$ 虚树边数 $+$ 标记点数 $-2\times$ 路径最大标记点数。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define MaxN 105000
using namespace std;
vector<int> g[MaxN];
char col[MaxN];int s[MaxN],ans;
void pfs(int u,int fa)
{
s[u]=col[u];
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=fa){
pfs(v,u);
s[u]+=s[v];
if (s[v]>0)ans+=2;
}
}
int f[MaxN],len;
void dfs(int u,int fa)
{
len=max(len,(int)col[u]);
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=fa){
dfs(v,u);
len=max(len,f[u]+f[v]+col[u]);
f[u]=max(f[u],f[v]);
}
f[u]+=col[u];
}
int n;
int main()
{
scanf("%d",&n);
for (int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].pb(v);g[v].pb(u);
}scanf("%s",col+1);
int rt=0;
for (int i=1;i<=n;i++)
if (col[i]=(col[i]=='W'))
rt=i;
if (!rt){printf("0");return 0;}
pfs(rt,0);
if (s[rt]==1){printf("1");return 0;}
for (int u=1;u<=n;u++)if (s[u]){
int cnt=0;
for (int i=0;i<g[u].size();i++)
cnt+=(s[g[u][i]]>0);
ans+=(col[u]=(cnt&1)^col[u]);
}
dfs(rt,0);
printf("%d",ans-2*len);
return 0;
}
```