G. Gangsters in Central City

偏执的太偏执、 2021-10-25 12:56 228阅读 0赞

> 给出一棵$1$为根节点的含$n$个节点的树，叶子节点都是房屋，在一个集合里面添加房屋和移除房屋。
> 
> 每一次添加和移除后，回答下面两个问题。
> 
> 1.  使得已选房屋都不能从根节点到达，最少需要砍多少条边。
> 
> 2.  在第$1$问最少砍去边的条件下，如何砍边使得从节点点开始走不能到达的非已选房屋数目最小，输出最小值。
> 
> 对于100%的数据 ， $2 ≤ n ≤ 10^5 , 1 ≤ q ≤ 10^5$

Solution :

首先观察到，第一问的答案。

非常容易证明的一个上边界是砍去所有合法的$u$和1的连边，其中合法的$u$表示既和$1$直接相连，且含有有已选被选叶子节点的$1$的直接儿子$u$

显然，这样构造是可以切断所有的已选房屋的。

如果不那么取，在一棵有被选叶子的子树中，如果不像上面一样构造，那么为了切断已选叶子，切边必须下移，显然，为了保证该子树已选叶子被截断，那么断边的数目必须递增。

所有对于第一问，贪心策略成立。

在第一问思考的基础上，我们进一步想，如果找到一个临界边，若砍掉其下面的边使得被选叶子节点被切断这些边数大于1了，而砍掉上面的那条边却恰好可以切断被选叶子节点，那么问题就解决了。

这个临界边是这个子树里面被选叶子节点集合的LCA与父亲那一条连边。

这就是第二问的贪心策略。

如何求一个点集在树上的LCA（深度最大的公共祖先）呢？

结论是：求出这个点集dfs序最小的一个点$u$，dfs序最大的一个点$v$，则$lca(u,v)$即为所求。

这是因为dfs序覆盖的范围是一个连续的区间。

> 　　假设有三个点，DFS序分别为a,p,b且a<p<b。那么我们断言LCA(a,p,b)=LCA(a,b)。
> 
> 　　这是因为：两个点的LCA，就是最近的同时包含它们的那个区间所代表的点。既然LCA(a,b)的区间包含了a和b，那也一定包含了位于a和b之间的p。
> 
> 　　因此，对于每任意三个点，只需要保存DFS序最大和最小的点。这个点集的LCA，也就是整个点集DFS序最小的和DFS序最大的这两个点的LCA。

至此，本题的理论部分就结束了，接下去就是实现的问题了。

首先对于每个叶子求出它对应属于根节点的那个子树zs\[u\]，对于每个节点求出其size\[\]表示含有叶子节点的数目。

ret表示当前被标记的叶子节点数目，ans1表示第一问的答案，ans2表示被上述贪心策略覆盖总点数。

显然，最后的答案是ans1, ans2 - ret;

对于每个根节点子树开个set，维护当中被标记节点的dfs序，每次只需要求最大和最小即可。

对于每个+和-分别维护就行了（动态更新ans1，ans2）。

复杂度是$O(n log\_2 n)$

# include <bits/stdc++.h>
    using namespace std; const int N=1e5+10; struct rec{ int pre,to; }a[N<<1]; int n,Q,dfn[N],tot,head[N],g[N][25],dep[N],size[N],zs[N],cnt[N]; struct node{ int x;}; bool operator < (node a,node b){
          return dfn[a.x]<dfn[b.x];} set<node>st[N]; char s[10]; void adde(int u,int v) { a[++tot].pre=head[u]; a[tot].to=v; head[u]=tot; } void dfs1(int u,int fa) { dfn[u]=++dfn[0]; g[u][0]=fa,dep[u]=dep[fa]+1; size[u]=0; bool leaf=1; for (int i=head[u];i;i=a[i].pre){ int v=a[i].to; if (v==fa) continue; dfs1(v,u); leaf=0; size[u]+=size[v]; } if (leaf) size[u]=1; } void dfs2(int u,int fa,int rt) { bool leaf=1; for (int i=head[u];i;i=a[i].pre) { int v=a[i].to; if (v==fa) continue; dfs2(v,u,rt); leaf=0; } if (leaf) zs[u]=rt; } void init() { for (int i=1;i<=21;i++) for (int j=1;j<=n;j++) g[j][i]=g[g[j][i-1]][i-1]; } int lca(int u,int v) { if (dep[u]<dep[v]) swap(u,v); for (int i=21;i>=0;i--) if (dep[g[u][i]]>=dep[v]) u=g[u][i]; if (u==v) return u; for (int i=21;i>=0;i--) if (g[u][i]!=g[v][i]) u=g[u][i],v=g[v][i]; return g[u][0]; } int main() { freopen("gangsters.in","r",stdin); freopen("gangsters.out","w",stdout); scanf("%d%d",&n,&Q); for (int i=2;i<=n;i++) { int u; scanf("%d",&u); adde(i,u); adde(u,i); } dfs1(1,0);init(); for (int i=head[1];i;i=a[i].pre) dfs2(a[i].to,1,a[i].to); int ans1=0,ans2=0,ret=0; while (Q--) { int d; scanf("%s%d",s,&d); if (s[0]=='+') { ret++; if (cnt[zs[d]]==0) ans1++;  cnt[zs[d]]++; int pre=0; if (st[zs[d]].size()!=0) { int u=(*(st[zs[d]].begin())).x,v=(*(--st[zs[d]].end())).x; pre=size[lca(u,v)]; } st[zs[d]].insert((node){d}); int u=(*(st[zs[d]].begin())).x,v=(*(--st[zs[d]].end())).x; int now=size[lca(u,v)]; ans2+=now-pre;   printf("%d %d\n",ans1,ans2-ret); } else { ret--; if (cnt[zs[d]]==1) ans1--;  cnt[zs[d]]--; int u=(*(st[zs[d]].begin())).x,v=(*(--st[zs[d]].end())).x; int pre=size[lca(u,v)]; st[zs[d]].erase((node){d}); int now=0; if (st[zs[d]].size()!=0) { u=(*(st[zs[d]].begin())).x,v=(*(--st[zs[d]].end())).x; now=size[lca(u,v)]; } ans2+=now-pre;  printf("%d %d\n",ans1,ans2-ret); } } return 0; }

转载于:https://www.cnblogs.com/ljc20020730/p/11260473.html