2020牛客暑期多校第二场 C - Cover the Tree（思维/贪心）-白红宇的个人博客

2020牛客暑期多校第二场 C - Cover the Tree（思维/贪心）

发布日期：2021-05-07 02:28:38 浏览次数：21 分类：精选文章

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

实际上这题只要“乱搞”就行，一开始以为大佬们说的乱搞是树链剖分什么的，这些还没开始学。然而其实就是贪心的思考一下，发现只需要叶子节点两两配对，首先从 $1$ 号节点跑一下 $d f s$ 按顺序找出叶子节点然后我们以从中间的节点为界限，左边和右边各找一对，如果找第一个和最后一个，第二个和倒数第二个…会发现如下情况不能覆盖所有边：

那么我们就左边第一个和右边第一个，左边第二个和右边第二个…当然需要注意的是奇数个叶子节点需要多加一组

#include 
   
    #include 
    #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define lowbit(x) (x&(-x))#define mkp(x,y) make_pair(x,y)#define mem(a,x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair
                
                  P;const double eps=1e-8;const double pi=acos(-1.0);const int inf=0x3f3f3f3f;const ll INF=1e18;const int Mod=1e9+7;const int maxn=2e5+10;int d[maxn];vector
                 
                   G[maxn];vector
                  
                    ans;void dfs(int u,int fa){ if(G[u].size()==1) ans.push_back(u); for(auto v: G[u]){ if(v!=fa) dfs(v,u); }}int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n; cin>>n; for(int i=0,u,v;i
                   
                    >u>>v; G[u].pb(v),G[v].pb(u); } dfs(1,0); //for(int i=0;i

上一篇：2020牛客暑期多校第二场 B - Boundary（简单计算几何）

下一篇：方阵（gcd+找规律）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章