[USACO18DEC]The Cow Gathering(洛谷-5157)(树-思维题)

题目描述

Luogu-传送门

思路

首先我们可以发现这是棵树
然后我们可以通过分析题目发现：
如果此时走的 人 牛不是叶节点,最终会剩下至少两个单独的节点,不符合题意
所以 我们每次删除只能删除叶节点
$(a,b)$ 表示 $a$ 必须比 $b$ 之前删

那么假设我们现在有棵树表示牛之间的关系(根节点任意)：

然后我们现在有几组 $(a,b)$

接下来开始骚操作：
首先将一个满足条件的点记为根节点，然后我们如果对每对 $(a,b)$ 连上 $a?>b$ 一条单向边的话,我们就发现我们每次删除的点必须是入度为1的点：

然后我们发现对于每个有向边(箭头),箭尾的子树肯定不是答案,因为你会发现箭头你删不掉…（因为必须把箭尾删了）
那么答案就是所有可行部分交集：

真丑…也就是
这些点
但是我们如何快速求交呢？

直接将 $(a,b)$ 中 $a$ 点标记一下就可以了,最后统计包含根节点且不包含标记点的联通块即可

代码

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();x*=f;return x;
}
#define MAXN 100000
#define INF 0x3f3f3f3f
queue<int> Q;
vector<int> G[MAXN+5],H[MAXN+5];
inline void Addedge(int u,int v){
    G[u].push_back(v);G[v].push_back(u);return ;
}
bool vis[MAXN+5];
int n,m,d[MAXN+5];
int BFS(){
    //d[i]:i号节点入度while(!Q.empty()){
    int u=Q.front();Q.pop();if(d[u]==0) return u;//只剩一个点for(int i=0;i<int(G[u].size());i++){
    int v=G[u][i];d[v]--;if(d[v]==1)//当前点为叶节点Q.push(v);}for(int i=0;i<int(H[u].size());i++){
    int v=H[u][i];d[v]--;if(d[v]==1)//当前点为叶节点Q.push(v);}}for(int i=1;i<=n;i++)puts("0");exit(0);return 0;
}
int ans[MAXN+5];
void DFS(int u,int fa){
    ans[u]=1;int siz=G[u].size();for(int i=0;i<siz;i++){
    int v=G[u][i];if(v==fa||vis[v]) continue;DFS(v,u);}
}
int main(){
    n=read(),m=read();for(int i=1;i<n;i++){
    int u=read(),v=read();Addedge(u,v);d[u]++,d[v]++;}for(int i=1;i<=m;i++){
    int u=read(),v=read();H[u].push_back(v);d[v]++,vis[u]=1;}for(int i=1;i<=n;i++)if(d[i]==1)Q.push(i);int Rt=BFS();DFS(Rt,0);for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0;
}

题外话

一道好题
如果觉得这篇文章还可以,请稍稍点一点个赞,作者感激不尽~~