AT_arc179_d [ARC179D] Portable Gate

AtCoder

以出发点为根，我们可以发现门一定在一个节点的祖先上，如果你走到一个点放下门，再继续走子树部分，然后去走其它子树时，一定会经过放门的这个点，那么此时这个门在这已经没有用了，如果你先去走其它子树，可以发现必定不是最优情况，所以门一定是在节点的祖先。

题目需要求出遍历完所有位置得到的答案。

我们需要对每个子树进行处理，由于问题是全部涂完色而不需要回到根，而对于根的子树需要先走回来才可以计入答案。

我们设 \(f_{i,0/1}\) 表示涂完 \(i\) 所在的子树所走的步数。

我们先考虑第一种情况，我们很容易想到我们在处理以一个节点所在的子树部分时，以此节点为根，对于这个节点的子树有节点放门和不放门两种情况。

假设此时的节点为 \(u\)，儿子节点为 \(v\)。

在不放门的情况下这一个子树的次数是为 \(f_{v,1}+2\) 。

而在放门的情况下，我们可以有一次不返回，直接传送回来，假设 \(siz_i\) 表示以 \(i\) 为根的子树中的节点数量，而 \(g_i\) 表示从 \(i\) 向子树内可以连到的最长链长度，也可以理解为最大深度。

此时次数就是 \(2\times (siz_i-1) - g_i\) 。

那么最后就可以得到 \(f_{u,1}\) 的转移式为：

\[$ f_{u,1}=\sum _{v\in son_u} \min(f_{v,1}+2,2\times (siz_v-1) - g_v)$\]

对于 \(f_{u,0}\) 我们只需要让一个子树不回来即可。

那么此时将上一次的这棵子树的答案减掉，然后再加上不用返回的情况即可，转移式为：

\[$ f_{u,0}=f_{u,1}-\max(\min(f_{v,1}+2,2\times (siz_v-1) - g_v)-\min(f_{v,0}+1,2\times (siz_v-1)-g_v+1)) $\]

这样就处理完成了，但是我们并不知道起点在哪里，所以要换根，后面就比较板子了。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,f[200005][2],g[200005][2],ma[200005][2],siz[200005],ans=1e18;
vector<int> e[200005];
void dfs(int p,int fa){siz[p]=1;for(int i:e[p]){if(i==fa)continue;dfs(i,p);}ma[p][0]=ma[p][1]=-1e16;for(int i:e[p]){if(i==fa)continue;f[p][1]+=min(f[i][1]+2,2*(siz[i]-1)-g[i][0]+1);if(g[i][0]+1>g[p][0])g[p][1]=g[p][0],g[p][0]=g[i][0]+1;else if(g[i][0]+1>g[p][1])g[p][1]=g[i][0]+1;siz[p]+=siz[i];int tmp=min(f[i][1]+2,2*(siz[i]-1)-g[i][0]+1)-min(f[i][0]+1,2*(siz[i]-1)-g[i][0]+1);if(tmp>ma[p][0])ma[p][1]=ma[p][0],ma[p][0]=tmp;else if(tmp>ma[p][1])ma[p][1]=tmp;}if(siz[p]==1)ma[p][0]=0;f[p][0]=f[p][1]-ma[p][0];
}
void dfs2(int p,int fa){ans=min(ans,f[p][0]);int fp0=f[p][0],fp1=f[p][1],gp0=g[p][0],map0=ma[p][0],sizp=siz[p];for(int i:e[p]){if(i==fa)continue;f[p][1]-=min(f[i][1]+2,2*(siz[i]-1)-g[i][0]+1);if(g[i][0]+1==g[p][0])g[p][0]=g[p][1];siz[p]-=siz[i];int tmp=min(f[i][1]+2,2*(siz[i]-1)-g[i][0]+1)-min(f[i][0]+1,2*(siz[i]-1)-g[i][0]+1);if(tmp==ma[p][0])ma[p][0]=ma[p][1];f[p][0]=f[p][1]-ma[p][0];swap(i,p);f[p][1]+=min(f[i][1]+2,2*(siz[i]-1)-g[i][0]+1);if(g[i][0]+1>g[p][0])g[p][1]=g[p][0],g[p][0]=g[i][0]+1;else if(g[i][0]+1>g[p][1])g[p][1]=g[i][0]+1;siz[p]+=siz[i];tmp=min(f[i][1]+2,2*(siz[i]-1)-g[i][0]+1)-min(f[i][0]+1,2*(siz[i]-1)-g[i][0]+1);if(tmp>ma[p][0])ma[p][1]=ma[p][0],ma[p][0]=tmp;else if(tmp>ma[p][1])ma[p][1]=tmp;f[p][0]=f[p][1]-ma[p][0];swap(i,p);dfs2(i,p);f[p][0]=fp0,f[p][1]=fp1,g[p][0]=gp0,ma[p][0]=map0,siz[p]=sizp;}
}
signed main(){cin>>n;for(int i=1,u,v;i<n;i++){cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}dfs(1,0);dfs2(1,0);cout<<ans;return 0;
}