正解:构造

解题报告:

传送门!

这题首先可以画下图找下规律,,,然后通过找规律可以发现,最终的方案一定是一条主干+一些枝条,而且这些枝条的分杈一定小于等于2

明确一下主干的定义,最左边的节点和最右边的节点之间的路径为主干

如图

CF573C Bear and Drawing 构造+树论

强行证明一下吼,,,

因为是两排平行的“钉子板”

所以如果一个分枝点想要有超过2个儿子结点

因为在同侧最多有两条边

就一定要往另一边伸至少一条边

这样就因为这条边挡住了一侧（比如说左侧）

那么剩下的边只能往右侧伸展了

那它向另一侧伸的边伸出的子树中的叶子节点一定有一个是最左边的节点

那最左边的节点的路径一定要经过它

所以它就在最左边的节点到最右边的节点的路上

它就是主干不是分枝辣

然后就考虑,我怎么找哪个是杈哪个是主干呐

那就从叶子节点开始,把链减下来,剩下的不是主干就是分杈点

然后就看,如果这个点麻油被减下来的邻居只有一个,说明那它就是分叉点或者主干点的最侧端

然后最后判断一下484所有主干的邻居主干点都小于等于2就好辣!

(最后分享一个傻逼错误,,,给大家提个醒,,,虽然我jio得不会有人和我一样蠢地犯这个错误QAQ

就是,我jio得这题过程中有很多次要算size,所以我就预处理了下sz存了下来

但是,我是一遍算sz一遍dfs

然后这就会导致,在dfs的时候可能会dfs到还麻油算sz的点

就会错误地删掉

就WA了,,,

我说开始错的时候找评测记录怎么一直没找到和我一样WA在第五个点的,,,原来是这个错误太sd辣一般人不会犯呜呜呜,,,

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define il inline
#define rg register
#define rp(i,x,y) for(rg ll i=x;i<=y;++i)
#define my(i,x,y) for(rg ll i=x;i>=y;--i)

const ll N=100000+10;
ll n,sz[N],lg[N];
bool del[N];
vector<ll>ed[N];

il ll read()
{
    rg char ch=getchar();rg ll x=0;rg bool y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar();
    if(ch=='-')ch=getchar(),y=0;
    while(ch<='9' && ch>='0')x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    return y?x:-x;
}
il void dfs(ll nw,ll sn){if(sz[nw]<=2){del[nw]=1;rp(i,0,sz[nw]-1)if(ed[nw][i]!=sn)dfs(ed[nw][i],nw);}}

int main()
{
    n=read();rp(i,1,n-1){ll x=read(),y=read();ed[x].push_back(y);ed[y].push_back(x);}
    rp(i,1,n)sz[i]=ed[i].size();rp(i,1,n)if(sz[i]==1)dfs(i,0);
    rp(i,1,n)rp(j,0,sz[i]-1)if(del[ed[i][j]])++lg[i];
    rp(i,1,n)
        if(!del[i])
        {
            ll cnt=0;
            rp(j,0,sz[i]-1)if(sz[ed[i][j]]-min(lg[ed[i][j]],2)>1 && (!del[i]))++cnt;
            if(cnt>2)return printf("No"),0;
        }
    return printf("Yes"),0;
}

这儿是代码!

View Code

CF573C Bear and Drawing 构造+树论

正解:构造

解题报告:

相关推荐