本文共 3451 字，大约阅读时间需要 11 分钟。

题目

思路

首先，朋友关系是树形的。下文中将直接使用图论的语言去称呼（而不是“奶牛”、“朋友圈”）。

“只要至少还有两头奶牛尚未离开，所有尚未离开的奶牛都还有没有离开的朋友。”

这句话想告诉我们什么？每次删去一个叶子节点（度数为一的节点）。

否则，如果删掉了非叶子节点，则图变为森林，将无法完成任务，你无法将任意一个连通块删除至只有一个点。

现在再看看我们要求解的问题，能否最后一个离开。如若能，将其设为根节点，则每一颗子树都是自底向上地删除。

暴力算法

先给出 $\mathcal{O}(n^2)$ 的算法，为后文的一些叙述做铺垫。

枚举这个根，并按照如下规则连有向边。

• 子节点向父节点连边。
• 如果 $a$ 需要比 $b$ 先离开，则 $a$ 向 $b$ 连边。

意义是显然的：一个点的所有入度都需要在其被删除之前删除。所以现在我们只需要进行一次 拓扑排序 检查是否有环即可（事实上，你同时也得到了一组合法的解）。

优化暴力

如果 $a$ 需要比 $b$ 先离开，那么 $a\to b$ ；此时，如果 $b$ 是 $a$ 子树内一点，那么 $b\to a$ ，形成了一个环，一定无解。

所以，如果我们有一个约束条件 $⟨a,b⟩$ ，即 $a$ 必须比 $b$ 先离开，那么根到达 $b$ 的路径上不能有 $a$ 。在代码实现的时候，我们只需要先钦定一个根，然后进行如下操作。

• 如果 $lca(a,b)\ne a$ ，则 $a$ 子树内都不可行；
• 否则，只有 $a$ 包含 $b$ 的儿子子树可行。

可以树上差分，每个点存储子树内的 $lazy$ 权值即可（详见代码）。

检测无解

这样就完了吗？其实，根到 $b$ 的路径上没有 $a$ 只是 $⟨a,b⟩$ 的必要条件罢了。这并不充分。

有可能很多约束条件合在一起，恰好使得新图中出现了环。下面，我们就要解决这一问题。

首先，所有未被排除的点形成了一个连通块。因为上面的操作都是针对连通块（子树）的。

现在，我们说明，这些没有被排除的点中，只要其中一个点不能为根，所有点都不能为根（即无解）！

利用反证法来证明。假设有至少一个点不能为根，但也存在一些点可以为根。则一定有“接壤”的两个点，其中一个可行，另一个不可行。考虑此二者在建图上的不同。

是的，我只想告诉你，相邻的点作为根，建图时的区别只有二者之间的连边！

这条边有没有可能在环上，成为压死骆驼的最后一个稻草呢？当然不可能！这条边的出点是根！

根，毫无疑问的，是不能比别的点先离开的（否则就会被排除），所以根只有入度，没有出度。

于是，这条改变了的边，丝毫不影响图中有环这一事实。证明完毕。

随便抽一个点出来，检查发育 检查是否无解即可。

代码

挺久以前写的了，没有注释，也不想加入注释给你们看

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAXN=100000;vector
       
         g[MAXN+2];int n,m;int fa[MAXN+2][20],depth[MAXN+2];void BuildTree(int x){   	for(int i=0,len=g[x].size(),y;i^len;++i){   		y=g[x][i];		if(y^fa[x][0]){   			fa[y][0]=x;			depth[y]=depth[x]+1;			BuildTree(y);		}	}}void prepare_lca(){   	for(int j=1;j^20;++j)		for(int i=1;i<=n;++i)			fa[i][j]=fa[fa[i][j-1]][j-1];}int get_lca(int a,int b){   	if(depth[a]
        
         >j&1) a=fa[a][j]; if(a==b) return a; for(int j=19;~j;--j) if(fa[a][j]!=fa[b][j]) a=fa[a][j],b=fa[b][j]; return fa[a][0];}int jump_close(int a,int b){ for(int j=19;~j;--j) if(depth[fa[a][j]]>depth[b]) a=fa[a][j]; return a;}int Down[MAXN+2];bool ans[MAXN+2];void get_ans(int x,int sum){ if((sum+=Down[x])>=0) ans[x]=1; for(int i=0,len=g[x].size(),y;i^len;++i){ y=g[x][i]; if(y^fa[x][0]) get_ans(y,sum); }}vector
         
           earlier[MAXN+2];int rd[MAXN+2];queue
          
            q;bool GetTopOrder(){ for(int i=1;i<=n;++i) if(rd[i]==1){ rd[i]=0; q.push(i); } int x; while(!q.empty()){ x=q.front(),q.pop(); for(int i=0,len=g[x].size();i^len;++i) if(--rd[g[x][i]]==1){ rd[g[x][i]]=0; q.push(g[x][i]); } for(int i=0,len=earlier[x].size();i^len;++i) if(--rd[earlier[x][i]]==1){ rd[earlier[x][i]]=0; q.push(earlier[x][i]); } } for(int i=1;i<=n;++i) if(rd[i]>0) return false; return true;}bool check_NoSolution(){ for(int i=1;i<=n;++i){ for(int j=0,len=g[i].size();j^len;++j) ++rd[g[i][j]]; for(int j=0,len=earlier[i].size();j^len;++j) ++rd[earlier[i][j]]; } return !GetTopOrder();}int main(){ scanf("%d %d",&n,&m); for(int i=1,x,y;i^n;++i){ scanf("%d %d",&x,&y); g[x].push_back(y); g[y].push_back(x); } BuildTree(1); prepare_lca(); for(int i=0,a,b;i^m;++i){ scanf("%d %d",&a,&b); earlier[a].push_back(b); int lca=get_lca(a,b); if(lca==a){ --Down[1]; ++Down[jump_close(b,a)]; } else --Down[a]; } if(check_NoSolution()) --Down[1]; get_ans(1,0); for(int i=1;i<=n;++i){ putchar((ans[i]?1:0)+'0'); puts(""); } return 0;}
          
         
        
       
      
     
    
   

转载地址：http://nhvq.baihongyu.com/